http://yxq0620.blog.163.com/blog/static/4449439220101132121273/
http://hi.baidu.com/feithor/item/f0d16911ae7036473a176e91
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\n",j,b[j],dp[j]);*/ 33 } 34 printf("%I64d\n",max); 35 } 36 return 0; 37 } 38 39 40