[백준] 연속합

이번에는 연속합을 구하는 알고리즘을 구하여봅니다

n = int(input())
num_list = list(map(int, input().split()))
temp = [0 for _ in range(n)]
result = -1001

for i in range(n):
    temp[i] = max(temp[i-1] + num_list[i], num_list[i])
    result = max(result, temp[i])
        
print(result)

왼쪽부터 더한 값과 현재 값 중의 max값 현재까지의 최댓값과 result 중의 max값 을 통하여 최댓값을 구할 수 있습니다 그리고 중간에 음수가 끼었지만 최댓값이 되는 경우의 수를 고려할 수 있으며시간 복잡도를 O(n) 안에 끝낼 수 있습니다.