#126 백준 파이썬 [1912] 연속합

https://www.acmicpc.net/problem/1912

 

#Solution

다음과 같은 알고리즘으로 최댓값을 구할 수 있다.

1) 왼쪽부터 더한 값과 현재 값 중의 max값

2) 현재까지의 최댓값과 result 중의 max값

 

이와 같은 알고리즘은 중간중간 최댓값을 계속 갱신해준다는 장점이 있다. 중간에 음수가 끼었지만 최댓값이 되는 경우의 수를 고려할 수 있다.

또한 시간 복잡도를 O(n) 안에 끝낼 수 있다.

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)