This is original link to the problem
this question is a typical dp problem .It’s need us to find the maximum sub region sum,and I tear apart the equation of dp to find the start point and terminate point .
#include<bits/stdc++.h> #include <cstring> #define maxn 100005 int dp[maxn]; int num[maxn]; int st[maxn]; int en[maxn]; using namespace std; int T=0; void islast(int t) { if(t!=T) { printf("\n"); } } int main() { scanf("%d",&T); for(int t=1;t<=T;t++) { memset(dp,0,sizeof(dp)); memset(en,0,sizeof(en)); memset(st,0,sizeof(st)); int n=0; int cnt=0,minus_n = -99999999,minus_index; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&num[i]); if(num[i]<0) { cnt++; if(minus_n < num[i]) { minus_index = i; minus_n = num[i]; } } } if(cnt==n) { printf("Case %d:\n",t); printf("%d %d %d\n",minus_n,minus_index,minus_index); islast(t); continue; } dp[1] = num[1]; en[1] = st[1] = 1; int ans=-1,index; for(int i=2;i<=n;i++) { //dp[i] = max(dp[i-1],0)+num[i]; if(dp[i-1]>=0) { dp[i] = num[i]+dp[i-1]; en[i] = i; st[i] = st[i-1]; } else { dp[i] = num[i]; st[i] = en[i] = i; } if(ans < dp[i]) { ans = dp[i]; index = i; } } /*for(int i=0;i<=n;i++) { cout<<dp[i]<<" "<<st[i]<<" "<<en[i]<<endl; }*/ printf("Case %d:\n",t); printf("%d %d %d\n",ans,st[index],en[index]); islast(t); //cout<<ans<<" "<<st[index]<<" "<<en[index]<<endl; //cout<<dp[n]<<" "<<st[n]<<" "<<en[n]<<endl; } return 0; }