[SWEA/3819] 최대 부분 배열

카데인 알고리즘 (1차원 DP) 

점화식

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int T; cin >> T;
	for (int tc = 1; tc <= T; ++tc) {
		int N; cin >> N;
		vector<int> v(N, 0);
		for (int i = 0; i < N; i++) cin >> v[i];
		int submax = v[0];
		int totmax = v[0];
		for (int i = 1; i < N; i++) {
			submax = max(v[i], submax + v[i]);
			totmax = max(totmax, submax);
		}
		cout << "#" << tc << " " << totmax << "\n";
	}
	return 0;
}