연속부분최대합L

문제

---

N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다.

 

입력

---

첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 1,000,000 ) 두 번째 줄에 n개의 정수가 주어진다.  

출력

---

연속된 부분을 선택하였을 때의 최댓값을 출력한다.

 

예제 입력

8
2 3 -5 8 -3 4 2 -9

예제 출력

11

 

예제 입력

5
-1 -2 3 -2 4

예제 출력

5

 

---

연속부분최대합을 동적계획법으로 푸는 풀이다.

Table(i) 를 i번째 수를 오른쪽 끝으로 하는 연속부분 중 최대합이라고 정의한다.

그러면 Table에 대한 점화식은 Table(i) = max ( Table(i-1) + Data(i) , Data(i) ) 가 된다.

위의 예제로 Table 을 구해보면 2  5  0  8  5  9  11  2 이므로, 이 값들중 가장 최대값인 11이 정답이 된다.

그러면 연속부분최대합을 완전 탐색법에서는 O(n^2) 분할 정복법에서는 O(nlogn) 동적계획법에서는 O(n) 만에 구할 수 있다.