最大m子段和问题 Max Sum Plus Plus —— 动态规划

“最大m子段和” 问题 Max Sum Plus Plus

问题描述：

给定由n个整数(可能为负数)组成的序列a1,a2,a3……an,以及一个正整数m,要求确定此序列的m个不相交子段的总和达到最大。最大子段和问题是最大m字段和问题当m=1时的特殊情形。

OJ题目源地址：

http://acm.hdu.edu.cn/showproblem.php?pid=1024

Max Sum Plus Plus

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

6
8

Hint
Huge input, scanf and dynamic programming is recommended.
 

结题思路：

见计算机算法设计与分析（第三版） 王晓东编著

源代码：

C++源代码（未优化版），算法时间复杂度O(m*n^2)， 空间复杂度O(mn)。

/*
* 数组a，大小为n，找出a中的最大子段和
* @para m - 最大子段个数
* @para n - 数组a的大小
* @para a - 数组指针地址（下标从零开始）
*/
int MaxSum(int m,int n,int *a)  
{  
   if ( n<m || m<1 ) return 0;
   int** b=new int * [m+1];
   for(int i=0; i<=m; i++) b[i]=new int[n+1];
   for(int i=0; i<=m; ++i) b[i][0]=0;
   for(int j=0; j<=n; ++j) b[0][j]=0;

   for(int i=1; i<=m; ++i){
		for( int j=i; j<=n-m+i; ++j){
			if(j>i){
				b[i][j] = b[i][j-1] + a[j-1];// 数组a的j-1下标指的是第j个元素。
				for( int t= i -1; t<j; ++t){
					b[i][j] = max(b[i][j], b[i-1][t] + a[j-1]);
				}
			}else{
				b[i][j] = b[i-1][j-1] + a[j-1];
			}
		}
    }
    int sum=0;
   	for( int j=m; j<=n; ++j){
		sum= max(sum, b[m][j]);
	}
	return sum;
}  

int main()  
{
	freopen("input.txt","r",stdin);
	int m,n;
	while(cin>>m>>n){
		int *a=new int[n];
		for(int i=0;i<n; ++i){
			cin>>a[i];
		}  
		cout<<MaxSum(m,n,a)<<endl;
	}
} 

其他参考资料：

http://blog.csdn.net/liufeng_king/article/details/8632430

http://www.acmerblog.com/hdu-1024-Max-Sum-Plus-Plus-1276.html

最大m子段和问题 Max Sum Plus Plus —— 动态规划,布布扣,bubuko.com

最大m子段和问题 Max Sum Plus Plus —— 动态规划

原文：http://blog.csdn.net/mason_mow/article/details/27368891