杭电 1003 Max Sum （动态规划）

参考：https://www.cnblogs.com/yexiaozi/p/5749338.html
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int N=1e5+10;
 6 int a[N],dp[N];
 7 int n;
 8 void test()
 9 {
10     cout<<"
---------
";
11     for (int i=0;i<=n;i++)
12     {
13         cout<<'['<<a[i]<<']';
14     }
15     cout<<endl;
16     for (int i=0;i<=n;i++)
17     {
18         cout<<'['<<dp[i]<<']';
19     }
20     cout<<"
------------
";
21 }
22 int main()
23 {
24     int t;
25 //    freopen("btext.txt","r",stdin);
26     while (cin>>t)
27     {
28         for (int ca=1;ca<=t;ca++)
29         {
30             cin>>n;
31             int ans=-N,s,e;
32             memset(a,0,sizeof(a));
33             memset(dp,0,sizeof(dp));
34             for (int i=1;i<=n;i++)
35             {
36                 cin>>a[i];
37                 dp[i]=max(dp[i-1]+a[i],a[i]);
38 //                test();
39                 if (dp[i]>ans)
40                 {
41                     ans=dp[i];
42                     e=i;
43                 }
44             }
45             int sum=0;
46             for (int i=e;i>=1;i--)
47             {
48                 sum+=a[i];
49                 if (sum==ans)//要求第一个例子，所以不能break!
50                 {
51                     s=i;
52                 }
53             }
54             cout<<"Case "<<ca<<':'<<endl;
55             cout<<ans<<' '<<s<<' '<<e<<endl;
56             if (ca!=t)//注意格式！
57             {
58                 cout<<endl;
59             }
60         }
61     }
62 
63     return 0;
64 }