首页 > 代码库 > 最大m子段和问题 Max Sum Plus Plus —— 动态规划
最大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
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. ^_^
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.
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 8HintHuge 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。