hdu1024 Max Sum Plus Plus(最大和子序列升级版)

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define M 999999999
 4 int a[1000001],b[1000001],dp[1000001];
 5 int Max(int x,int y)
 6 {
 7     return x>y?x:y;
 8 }
 9 //b[j]为到当前元素最大和子序列的最大和
10 //dp[j]为到当前元素的最大和序列的最大和
11 int main()
12 {
13     int m,n,i,j;
14     while(scanf("%d%d",&m,&n)!=-1)
15     {
16         for(i=1;i<=n;i++)
17             scanf("%d",&a[i]);
18         __int64 max;
19         memset(b,0,sizeof(b));
20         memset(dp,0,sizeof(dp));
21         for(i=1;i<=m;i++)
22         {
23             max=-M;
24             for(j=i;j<=n;j++)
25             {
26                 dp[j]=Max(dp[j-1],b[j-1])+a[j];
27                 b[j-1]=max;
28                 if(max<dp[j])
29                     max=dp[j];
30             }
31         /*    for(j=1;j<=n;j++)
32                 printf("%d   %d  %d
",j,b[j],dp[j]);*/
33         }
34         printf("%I64d
",max);
35     }
36     return 0;
37 }
38 
39 
40