[C++]BOJ 1912 - 연속합

합이 가장 큰 연속된 부분집합을 찾는 문제로 dp[i - 1] + i번째 수와 i번째 수 중 큰 것을 dp[i]에 저장한다.

1. dp[i - 1] + i번째 수
2. i번째 수

1번이 더 크다면 dp[i - 1]가 양수고, 2번이 더 크다면 dp[i - 1]가 음수다.

가장 큰 부분합이 마지막 원소를 포함하지 않는다면 마지막 위치에 저장되지 않을 수 있으므로 dp[]를 정렬해서 부분합 중 가장 큰 것을 고른다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, dp[100001] = {-1001, };
int main() {
	cin >> n;
	for(int i = 1; i <= n && cin >> m; i++)
		dp[i] = max(dp[i - 1] + m, m);
	sort(dp, dp + n + 1);
	cout << dp[n];
}