题目链接：https://vjudge.net/problem/HDU-1024
简单题意：长度为n的数列，选出m个连续子段，求出它们的最大和
这题以前做过，但是代码写烦了，今天重写了一次。设f[i][j]表示以j结尾，将前j个数选出i段的最大和，则有：
f[i][j]=max(f[i][j-1]+a[j],f[i-1][k]+a[j]),i-1<=k<=j-1
但是直接用这个式子的话，时间和空间都不够。f[i][j]只和f[i][?]和f[i-1][?]有关，可以用一个新的数组p保存f[i-1][?]，这样空间复杂度降为O(n)；同时可以用一个变量记录f[i-1][k]的最大值，时间复杂度O(n*m)
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e6+10;
ll f[N],p[N];
int a[N],n,m,i,j;
int main(){
while (~scanf("%d%d",&m,&n)){
for (i=1;i<=n;i++) {
scanf("%d",&a[i]); p[i]=0;
}
for (i=1;i<=m;i++){
ll tmp=-1e12;
for (j=i;j<=n;j++){
tmp=max(tmp,p[j-1]);
f[j]=max(f[j-1]+a[j],tmp+a[j]);
}
for (j=1;j<=n;j++) p[j]=f[j];
}
ll ans=-1e12;
for (i=m;i<=n;i++) ans=max(ans,f[i]);
printf("%lld\n",ans);
}
return 0;
}
原文：https://www.cnblogs.com/edmunds/p/13605206.html