最大m子段和

tonyfang posted @ 2015年8月13日 20:31 in Algorithm with tags c++ Algorithm , 384 阅读

本文介绍最大$m$子段和。

问题描述:在$n$个数的序列$A_1, A_2, A_3, ..., A_n$中选出连续不相交的$m$个子段,使得这$m$个子段的和最大。

首先介绍朴素做法:

$f_{i,j}$表示数组前$j$项,$i$个子段和的最大值,且第$i$个子段含有$a_j$。

那么所求的最优值显然为$max(f_{m,j})$,$j→[m,n]$

那么$f_{i,j}=max(f_{i,j-1}+a_j,max(f_{i-1,t})+a_j)$,$t→[i-1,j-1]$。

其中,$f_{i,j-1}+a_j$表示第i个子段含$a_j$;$max(f_{i-1,t})+a_j$ 表示第i个子段目前只有$a_j$

初始时,$f_{0,j}=0,f_{i,0}=0$。

这样的DP的复杂度为$O(mn^2)$,空间复杂度为$O(nm)$,并不令人满意。

首先,转移只用到$f_{i,x}$或$f_{i-1,x}$,所以可以滚动数组记录。

另一方面$max(f_{i-1,t})$ 可以在计算 $f_{i-1,x}$的时候记录下来即可,这样,算法空间复杂度被优化到了$O(n)$,时间复杂度为$O(n(n-m))$,可以应对一般的题目了。

代码见下方:(HDU 1024 最大m字段和:这里

#include <stdio.h>
#define max(a,b) (a>b?a:b)
using namespace std;
int m,n,a[1001000];
int getsum() {
	if(n<m || m<1) return 0;
	int *b,*c; b=new int[n+1],c=new int[n+1];
	// b:前一行,c:这一行. 
	for (int i=0;i<=n;++i) b[i]=c[i]=0;
	int maxx;
	for (int i=1;i<=m;++i) {
		maxx=-2147483647;
		for (int j=i;j<=n;++j) {
			c[j]=max(b[j-1],c[j-1])+a[j];
			b[j-1]=maxx;			// 记录下上个最大值 
			if(c[j]>maxx) maxx=c[j];
		}
	}
	delete[]b;
	delete[]c;
	return maxx;
}
int main() {
	while(~scanf("%d%d",&m,&n)) {
		for (int i=1;i<=n;++i) scanf("%d",&a[i]);
		printf("%d\n",getsum());
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter