本文介绍最大$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;
}