연속 부분합의 최댓값

문제

N개의 정수가 일렬로 있다. 여기서 연속된 몇 개의 정수를 고를 때, 그 합의 최댓값을 구하라. 단, 적어도 하나는 반드시 골라야 한다.

예: [-2, 1, -3, 4, -1, 2, 1, -5, 4]에서 최대 부분합은 6이다 (부분 배열 [4, -1, 2, 1]).

Kadane's algorithm을 쓰면 O(N)에 풀 수 있다.

cur = a[0]; best = a[0];
for i = 1..N-1:
    cur = max(cur + a[i], a[i])
    best = max(best, cur)

입출력 예시

입력 1

9
-2 1 -3 4 -1 2 1 -5 4

출력 1

6

입력 2

5
-1 -2 -3 -4 -5

출력 2

-1