3장 다이나믹 프로그래밍 - (4) 문제 풀이 5 [1912번 - 연속합]

d[i] : a[i]를 마지막에 포함하는 가장 큰 연속합

d[i]=max(d[i-1]+a[i], a[i]) 

정답 : max(d[i])

#include <iostream>

#include <algorithm>

using namespace std;

int d[100001];

int a[100001];

int main(void) {

int n;

cin >> n;

for (int i = 1; i <= n; i++) {

cin >> a[i];

}

d[1] = a[1];

for (int i = 2; i <= n; i++) {

d[i] = max(d[i - 1] + a[i], a[i]);

}

int result = d[1];

for (int i = 2; i <= n; i++) {

if (result < d[i])

result = d[i];

}

cout << result << endl;

return 0;

}