Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 330535 Accepted Submission(s): 78678
2 5 6 -1 5 4 -7 7 0 6 -1 1 -6 7 -5
Case 1: 14 1 4 Case 2: 7 1 6
就是给你一个序列，求最大区间和以及该最大区间的下标
动态规划的思想：
用dp[i]来代表以a[i]为结尾的最大区间和，这样就有两种情况：
要么dp[i]是正的 那么以a[i]结尾的最大区间和就是dp[i-1]+a[i]（因为必须是a[i]结尾，a[i]是正是负都无法取舍的）
要么dp[i]是负的 那么以a[i]结尾的最大区间和就是a[i]
状态转移方程：dp[i] = max( dp[i-1]+a[i], a[i] );
初始化：因为我们从前往后推，可以将dp数组和a数组合二为一，节约空间
另外需要注意的是 需要三个游标：s、l、r 分别代表当前区间的左端点、最大区间的左端点、最大区间的右断点，至于当前区间的右端点，可以直接用i表示。
#include<bits/stdc++.h> using namespace std; int T,n,i,dp[100005],l,r,s,maxs,t=0; int main() { cin>>T; while(T--) { t++; memset(dp,0,sizeof(dp)); cin>>n; for(i=1;i<=n;i++) { scanf("%d",&dp[i]); } maxs=dp[1]; s=1; l=1; r=1; for(i=2;i<=n;i++) { dp[i]=max(dp[i-1]+dp[i],dp[i]); if(dp[i-1]<0) { s=i; } if(dp[i]>maxs) { l=s; r=i; maxs=dp[i]; } } printf("Case %d:\n",t); printf("%d %d %d\n",maxs,l,r); if(T) printf("\n"); } }
原文：https://www.cnblogs.com/dyhaohaoxuexi/p/11336609.html