hdoj-1003及动态规划理解

　求最大连续子数组之和

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.

 1 #include <stdio.h>
 2 int main()
 3 {
 4     int n=0;
 5     scanf("%d",&n);
 6     for (int i=1;i<=n;i++)
 7     {
 8         int sum=0,begin=0,end=0,temp=1,m=0;
 9         long max=-100000;
10         int a=0;
11         scanf("%d",&m);
12         for(int j=1;j<=m;j++)
13         {
14             scanf("%d",&a);
15             if(sum>=0)
16             {
17                 sum+=a;
18             }
19             else
20             {
21                 sum=a;
22                 temp=j;
23             }
24             if(sum>max)
25             {
26                 max=sum;
27                 begin=temp;
28                 end=j;
29             }
30         }
31         printf("Case %d:
",i);
32         printf("%d %d %d
",max,begin,end);
33         if (i != n)
34             printf("
");
35     }
36     return 1;
37 }

该问题类似背包问题，动态规划公式如下：

s[1] = a[1];

s[n] = s[n-1]>=0?s[n-1]+a[n]:a[n];