HDU1024 Max Sum Plus Plus

问题描述：最长n段连续子序列和

1 3 1 2 3
2 6 -1 4 -2 3 -2 3

6
8

算法思想：

dp[i][j]保存前j个元素（包括j）分成i段最长连续子序列和

则有dp[i][j]=max(dp[i][j-1]+num[j],max(dp[i-1][t]+num[j]))     0<t<j

#include <iostream>
using namespace std;

int *s;
int m,n;
int maxL;
int *pre,*now;
int main()
{
	freopen("C:\\in.txt","r",stdin);
	
	while(scanf("%d %d",&m,&n)!=EOF){
		s=new int[n+1];
		pre=new int[n+1];
		now=new int[n+1];
		for(int i=0;i<=n;i++){now[i]=0;pre[i]=0;}
		for(int i=1;i<=n;i++){
			scanf("%d",&s[i]);
		}
		for(int i=1;i<=m;i++){
			maxL=-0x7fffffff;
			for(int j=i;j<=n;j++){
				now[j]=(now[j-1]>pre[j-1]?now[j-1]:pre[j-1])+s[j];
				pre[j-1]=maxL;
				if(maxL<now[j])
					maxL=now[j];
			}
		}
		printf("%d\n",maxL);
		delete[] s;
	}
	return 0;
}

HDU1024 Max Sum Plus Plus

原文：http://blog.csdn.net/starcuan/article/details/18893517