Max Sum

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 123917 Accepted Submission(s): 28659

Problem Description

Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

Input

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

Output

For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

Sample Input

5 6 -1 5 4 -7

7 0 6 -1 1 -6 7 -5

Sample Output

Case 1: 14 1 4

Case 2: 7 1 6

　　这一题的解题方法有很多种，而且这一题并不是第一次见到，只是做了好几次都做不出来(好吧，我承认自己不太会DP= =)这一题的方法可以用DP，可以用分治，一开始的做法我都是用分治，结果一直wa,然后现在换成了DP的解法，由于DP不是很懂，所以看了一下别人的解法= =。

　　解法是这样的：我们要求最大的一段数字的和，那么我们从一个方向入手，向另一个方向扫描，并记录一段当前可能是最大值得序列的其实和末尾；如果这个当前最大值比总体的最大值还要大，那么就用这个当前的最大值代替总体的最大值，如果当前最大值加上第i个数以后比以前还要小，那么就从第i个位置开始算起作为当前最大值。总之感觉描述有点模糊，毕竟还是不太了解，详细看代码。

 1 #include <cstdio>
 2 #include <cstring>
 3 #define MAX 100001
 4 using namespace std;
 5 
 6 int a[MAX];
 7 int n;
 8 
 9 int main()
10 {
11     int t,pos,st,ed,maxn,sum;
12     scanf("%d",&t);
13     for(int i=1;i<=t;i++){
14         scanf("%d",&n);
15         for(int j=0;j<n;j++){
16             scanf("%d",&a[j]);
17         }
18         ed=st=pos=0;
19         maxn=sum=a[0];
20         for(int j=1;j<n;j++){
21             if(sum+a[j]<a[j]){            //加上当前位置的数以后最大值会变小，或者是前面的当前最大值是负数
22                 pos=j;
23                 sum=a[j];
24             }else{                        //序列还在上升，所以暂定最大值继续累加。
25                 sum+=a[j];
26             }
27             if(sum>maxn){                 //判定暂定的最大值是不是全体最大值，如果是就将全体最大值替换
28                 maxn=sum;
29                 st=pos;
30                 ed=j;
31             }
32         }
33         printf("Case %d:
%d %d %d
",i,maxn,st+1,ed+1);
34         if(i!=t) printf("
");
35     }
36     return 0;
37 }

1003