(동적계획법) 연속 부분 최대합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

 

---

/*
동적 계획법
연속 부분 최대합
A[i]를 오른 쪽 끝으로 갖는 구간의 최대 합을 반환하는 함수 maxAt(i)
A[i]에서 끝나는 최대 합 부분 구간은 항상 A[i] 하나만으로 구성되어 있거나, 
A[i-1]를 오른쪽 끝으로 갖는 최대 합 부분 구간의 오른쪽에 A[i]를 붙인 형태로 구성되어 있음을
증명할 수 있다.
 
점화식 >> maxAt(i) = max(0, maxAt(i-1)) + A[i]
 
*/
 
#include <stdio.h>
#include <vector>
using namespace std;
 
vector <int> A;
 
int n, m;
 
int fastestMaxSum(const vector<int>& A){
  int N = A.size(), ret = -987987987, psum = 0;
  for(int i = 0; i < N; ++i){
    psum = max(psum, 0) + A[i];
    ret = max(psum, ret);
  }
  return ret;
}
 
int main() {
 
 scanf("%d", &n);
 for(int i = 0 ; i < n; i++){
   int v;
   scanf("%d", &v);
   A.push_back(v);
 }
 
  int result = fastestMaxSum(A);
  printf("%d", result);
 
  return 0;
}