发现自己变懒了，不想详细写思路了
简单思路：计算n个数m段的子序列最大和，即计算前n个数m段的最大子序列和，前n个数,m段，马上想到这是动态规划,假设prior[n][m]代表前n个数m段子序列最大和，现在我们已经选出来了m段，可以考虑前n个数这m段包括第n个数在内吗？？分两种情况：包括与不包括，不包括就是第n个数没用了，也就就转化为前n-1个数m段最大子序列和prior[n-1][m]，如果包括则假设前n个数m段且包括第n个数为：present[n][m];
所以prior[n][m]=max(prior[n-1][m],present[n][m]);
同时易知present[n][m]=max(present[n-1][m]+s[n],prior[n-1][m-1]+s[n]);
把n,m换成j,i就得到了状态转移方程：present[j][i]=max(present[j-1][i]+s[j],prior[j-1][j-1]+s[j]);
prior[j][i]=max(prior[j-1][i],present[j][i]);
于是有下面初步代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;
const int MAX=100;
//分别代表前i个数j段且包括第i个数的最大值和前i个数j段的最大值
int present[MAX][MAX],prior[MAX][MAX];
int s[MAX];
int main(){
int m,n;
while(cin>>m>>n){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
present[i][j]=prior[i][j]=-INF;
}
}
for(int i=1;i<=n;++i)cin>>s[i];
for(int i=1;i<=m;++i){
for(int j=i;j<=n;++j){
present[j][i]=max(present[j-1][i]+s[j],prior[j-1][i-1]+s[j]);//包括第j个数的前j个数i段的最大值
prior[j][i]=max(prior[j-1][i],present[j][i]);//前j个数i段的最大值：不包括第j个数即前j-1个数i段最大值或者包括了第j个数即前j个数i段的最大值
}
}
cout<<prior[n][m]<<endl;
}
return 0;
}
由于本题n,m很大所以不能使用二维数组，会超内存，观察那个动态转移方程可以发现计算i,j时只需要用到j-1的情况，所以考虑省掉第二维数组且采用滚动数组:
present[j]=max(present[j-1]+s[j],prior[j-1]+s[j]);prior[j-1]=max(present[j-1],prior[j-2]);
prior[n]=max(present[n],prior[n-1]);
这里稍微改变下引入sum来存最大值，至于为什么在写代码中会明白，这里就不多说了。
下面是正确代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;
const int MAX=1000001;
int *s,*present,*prior;
//present代表前j个数且包括第j个数的i段子序列最大和,prior表示前j个数i段子序列的最大和
int main(){
int m,n;
while(cin>>m>>n){
s=new int[n+1];
for(int i=1;i<=n;++i)scanf("%d",s+i);
present=new int[n+1];
prior=(int *)calloc(n+1,sizeof(int));//calloc和maccoc区别在于它分配的内存连续且已对数据初始化为0
present[0]=0;//只需要对present[0]初始化,因为present[n]可以由present[n-1]得到
int sum=0;
for(int i=1;i<=m;++i){
sum=-INF;
for(int j=i;j<=n-m+i;++j){//m段时对应最少计算前n个数,m-1段时对应最少要计算前n-1个数,...i段对应最少要计算前n-m+i个数
//present[j-1]在这里代表前j-1个数i段序列的最大值,当j=j-1时就已经计算了present[j-1]
//prior[j-1]在这里代表前j-1个数i-1段序列的最大值,因为还没更新prior[j-1]为i段的最大值
present[j]=max(present[j-1]+s[j],prior[j-1]+s[j]);//将第j个数连载前i段的最后面或者自成一段与前i-1段合成i段
prior[j-1]=sum;//更新为前j-1个数i段的最大值,sum就是前j-1个数i段的最大值
sum=max(present[j],sum);//计算前j个数i段的最大值
}//present[j]=max(present[j-1]+s[j],prior[j-1]+s[j]);prior[j-1]=(present[j-1],prior[j-2]);
prior[n-m+i]=sum;//prior[n]=max(present[n],prior[n-1]);
}
cout<<sum<<endl;
delete[] s;
delete[] present;
delete[] prior;
}
return 0;
}
http://acm.hdu.edu.cn/showproblem.php?pid=1024
注释之后排版有点乱，下面是未注释的：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;
const int MAX=1000001;
int *s,*present,*prior;
int main(){
int m,n;
while(cin>>m>>n){
s=new int[n+1];
for(int i=1;i<=n;++i)scanf("%d",s+i);
present=new int[n+1];
prior=(int *)calloc(n+1,sizeof(int));
present[0]=0;
int sum=0;
for(int i=1;i<=m;++i){
sum=-INF;
for(int j=i;j<=n-m+i;++j){
present[j]=max(present[j-1]+s[j],prior[j-1]+s[j]);
prior[j-1]=sum;
sum=max(present[j],sum);
}
prior[n-m+i]=sum;
}
cout<<sum<<endl;
delete[] s;
delete[] present;
delete[] prior;
}
return 0;
}