백준 알고리즘 기초 강좌
3장 다이나믹 프로그래밍 - (4) 문제 풀이 5 [1912번 - 연속합]
살구르
2017. 8. 20. 15:46
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;
}