[DP] 최대 연속 부분합

Time Limit: 1000 msMemory Limit: 256 MBBronze III2Author: 관리자

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

Problem Statistics

3

Total submissions

1

Accepted

33.3%

Acceptance rate

1

Unique solvers

,

…

,

AN−1

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

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

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

입력

첫 줄에 $N$ ( $1 \le N \le 10^5$ ). 둘째 줄에 정수 $N$ 개 ( $-10^4 \le A_i \le 10^4$ ).

출력

최대 연속 부분합.

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