[DP] 최대 연속 부분합

문제

길이 $N$인 정수 배열 $A_0, A_1, \ldots, A_{N-1}$이 주어진다. 연속한 한 개 이상의 원소를 골라 만든 부분 배열의 합 중 가장 큰 값을 구하라. 원소에 음수가 섞일 수 있고, 적어도 한 개는 골라야 한다.

접근

$dp[i]$를 "$i$번 원소로 끝나는 부분 배열의 최대 합"이라 하면, 앞을 이어 붙일지 여기서 새로 시작할지 둘 중 큰 쪽이다.

$dp[i] = \max(A_i, \; dp[i-1] + A_i)$

답은 모든 $dp[i]$ 중 최댓값이다. 변수 하나로 굴리면 $O(N)$, 메모리 $O(1)$.

입출력 예시

입력:
9
-2 1 -3 4 -1 2 1 -5 4
출력: 6