首页 > 代码库 > 最大m子段和问题 Max Sum Plus Plus —— 动态规划

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

2024-07-06 18:52:07   226人阅读

“最大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

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 15863    Accepted Submission(s): 5153


Problem Description
Now I think you have got an AC in Ignatius.L‘s "Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.

Given a consecutive number sequence S1, S2, S3, S4 ... Sx, ... Sn (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ Sx ≤ 32767). We define a function sum(i, j) = Si + ... + Sj (1 ≤ i ≤ j ≤ n).

Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i1, j1) + sum(i2, j2) + sum(i3, j3) + ... + sum(im, jm) maximal (ix ≤ iy ≤ jx or ix ≤ jy ≤ jx is not allowed).

But I`m lazy, I don‘t want to write a special-judge module, so you don‘t have to output m pairs of i and j, just output the maximal summation of sum(ix, jx)(1 ≤ x ≤ m) instead. ^_^
 

Input
Each test case will begin with two integers m and n, followed by n integers S1, S2, S3 ... Sn.
Process to the end of file.
 

Output
Output the maximal summation described above in one line.
 

Sample Input
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
 

Sample Output
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


联系
我们