和前面的基本一样，本来想写个状态转移方程来的，结果没想到还是和前面的一样.....
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; int t,n; const int inf=-0x3f3f3f3f; const int maxn=100000+10; int a[maxn]; int dp[maxn]; int main() { scanf("%d",&t); for(int zz=1;zz<=t;zz++) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int s,e,st,ed,ans; s=e=st=ed=1; dp[1]=ans=a[1]; for(int i=2;i<=n;i++) { if(dp[i-1]>=0) { dp[i]=dp[i-1]+a[i]; ed=i; } else { dp[i]=a[i]; st=ed=i; } if(dp[i]>ans) { s=st; e=ed; ans=dp[i]; } } printf("Case %d:\n%d %d %d\n",zz,ans,s,e); if(zz!=t) printf("\n"); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7363432.html
