最大m子段和

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

本文介绍最大$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;
}
Online CUB 说:
2022年8月02日 16:51

City Union bank is a private authorized bank in India that provides various facilities to its account holders. With the growing banking structure, Online CUB change in dynamics, and number of private players entering in the banking sector of India. This will change work culture, competitive environment, a customer also requires their banking services at their doorsteps.Gone are the days, when people used to stand in the queues for transactions, balance check, or money transfers. Therefore, like other banks in India, City union bank also provides its users with the Online banking facility.


登录 *


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