Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 198961 Accepted Submission(s): 46506
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int MAXN=100005; int dp[MAXN]; int a[MAXN]; int n; int main() { int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); int maxn=dp[0]=a[0]; int l=0,r=0,ll=0,rr=0; for(int i=1;i<n;i++) { if(dp[i-1]>=0) { dp[i]=dp[i-1]+a[i]; r++; } else { l=r=i; dp[i]=a[i]; } if(dp[i]>maxn) { maxn=dp[i]; ll=l; rr=r; } } printf("Case %d:\n",cas); printf("%d %d %d\n",maxn,ll+1,rr+1); if(cas!=T) printf("\n"); } return 0; }
原文:http://www.cnblogs.com/program-ccc/p/5221992.html