这是一道DP入门题目，知识点是“最大连续子序列”
题目大意：给你一个长度为n的数字序列，取其中一段连续的序列，要求和最大；
分析：这是一道裸题，没有什么花里胡哨的东西，主要是写出状态转移方程
dp[i] = max{dp[i-1] + A[i], A[i]};
dp[i]是以i位置为结尾位置的最优解。
对于i位置上的A[i],一定对dp[i]做出了贡献。
对于i以前的位置，他们的最优解是dp[i-1],当dp[i-1]>=0时，dp[i-1]对dp[i]做出了贡献;反之，dp[i-1]对dp[i]有消极的作用；
我的错误：1.边界dp[1]忘记做了处理
2.要每次更新起点，铁憨憨我直接把最后更新后的结果当结果了。。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 const int Maxn = 100000 + 5; 6 int T,n; 7 int dp[Maxn]; 8 int main() 9 { 10 scanf("%d",&T); 11 for(int t=1;t<=T;t++) 12 { 13 scanf("%d",&n); 14 for(int i=1;i<=n;i++) 15 scanf("%d",&dp[i]); 16 int ans = dp[1];//用边界对ans初始化 17 int start = 1,ends = 1,fstart=1; 18 for(int i=2;i<=n;i++) 19 { 20 if(dp[i-1]>=0) 21 dp[i] += dp[i-1]; 22 else 23 start = i;//起点的更新不一定是最优解 24 if(dp[i] > ans) 25 { 26 ans = dp[i]; 27 fstart = start;//在更新最优解的时候更新起点 28 ends = i; 29 } 30 } 31 if(t!=1) puts(""); 32 printf("Case %d: ",t); 33 printf("%d %d %d ",ans,fstart,ends); 34 } 35 return 0; 36 }