最大子序列动态规划代码
#include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <map> using namespace std; const int inf = 0x3f; const int INF = 0x3f3f3f3f; const int maxn = 100005; int n, a[maxn], b[maxn]; int main() { int T; scanf("%d", &T); for(int tt = 1; tt <= T; tt++) { scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); } b[0] = a[0]; int ans = a[0], s = 0, t = 0, e = 0; for(int i = 1; i < n; i++) { if(a[i] > a[i]+b[i-1]) { t = i; b[i] = a[i]; } else { b[i] = a[i] + b[i-1]; } //printf("i = %d, %d\n", i, b[i]); if(b[i] > ans) { s = t; e = i; ans = b[i]; } } printf("Case %d:\n", tt); printf("%d %d %d\n", ans, s+1, e+1); } return 0; }
动态规划 挺好的 教程
原文:http://www.cnblogs.com/tenlee/p/4531767.html