hdu 1003 Max Sum 动态规划

Max Sum

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

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

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

DP 动态规划的题。这道题很久以前就看过 ，那个时候还不知道什么动态规划， 用暴力求解 ， 总是TLE。 今天从算法书上看了点动态规划的知识。终于顺利 把此题AC了。但过程还是花了很久。 因为我一直把 最大子序列的和 maxsum 初值定为 0 ， 没考虑全为负数！ 关于DP,今晚刚开始看，所以还需要点时间。 这道题 思路写在注释中。

01.#include<stdio.h>  
02.#define MAXN 100000  
03.int a[MAXN];  
04.int main()  
05.{  
06.    //freopen("scar.in","r",stdin);  
07.    int n,t,i,j;  
08.    while(scanf("%d",&n)!=EOF)  
09.    {     
10.       for(j=1;j<=n;j++)  
11.        {  
12.            int temp=0,maxsum,head,end,x=1;  //head,end是始末位置。  
13.                scanf("%d",&t);  
14.            for(i=0;i<t;i++)  
15.                scanf("%d",&a[i]);  
16.            maxsum=a[0];           //maxsum的初始值是a[0]。不要写成0  
17.            for(i=0;i<t;i++)  
18.            {  
19.              /*计算子序列的和。这里我的理解是如果前一段子序列  
20.              的和为负，还不如不加，重新开始算一段新的子序列的和。*/  
21.                if(temp>=0)             
22.                   temp+=a[i];  
23.               else                   //以新的起点重新开始另一段子序列的和。  
24.               {  
25.                   temp=a[i];  
26.                   x=i+1;  
27.               }  
28.               if(temp>=maxsum)    //从计算出的子序列和中选出最大的子序列和。      
29.               {  
30.                   maxsum=temp;  
31.                   end=i+1;  
32.                   head=x;  
33.               }  
34.            }  
35.               printf("Case %d:\n",j);  
36.               printf("%d %d %d\n",maxsum,head,end);  
37.               if(j!=n) printf("\n");  
38.        }  
39.    }  
40.    return 0;  
41.}