杭电 1003 Max Sum （动态规划）

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

2
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

大意：　
　　给出一个序列，求出序列中连续的数的和的最大值并输出连续数列中首尾的位置，比如6 -1 5 4 -7 中6-1+5+4=14为连续数列中和最大的。
　　输入：
　　　　先输入t，表示t组测试数据；
　　　　每组测试数据第一个数为序列的个数；
　　输出：
　　　　输出要求的最大和，和求出的序列的首尾位置。
思路：
　　用数组a[]记录序列中的数，对于a[i]只有两种可能   1.为一个序列的首  　2.为一个序列的尾 　用数组d[i]记录以第i个数结尾的序列的最大和，则
　　d[i]=max(d[i-1]+a[i],a[i])，d[i-1]+a[i]和a[i]分别对应a[i]的两种情况。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<string.h>
 4 using namespace std;
 5 int a[100000+11];
 6 int d[100000+11];
 7 int main()
 8 {
 9     int t;
10     scanf("%d",&t);
11     int k=0;
12     while(t--)
13     {
14         int sum=0;
15         int n,begin,end;    
16         int max0=-1001;                            //max0必须小于所有可能的整数 
17         scanf("%d",&n);
18         memset(a,0,sizeof(a));
19         memset(d,0,sizeof(d));
20         for(int i = 1 ; i <= n ; i++)
21         {
22             scanf("%d",&a[i]);
23             d[i]=max(d[i-1]+a[i],a[i]);
24             if(max0 < d[i])
25             {
26                 max0=d[i];                        //记录序列和的最大值 
27                 end=i;                            //记录和最大的序列的尾 
28             }
29         }
30         for(int i = end ; i >= 1 ; i--)
31         {
32             sum+=a[i];
33             if(sum == max0)
34             {
35                 begin=i;
36             }
37                 
38         }
39         printf("Case %d:
",++k);
40         printf("%d %d %d
",max0,begin,end);
41         if(t)
42         {
43             printf("
");                //注意输出格式 
44         }
45         
46     }
47 }