/*
dp[i][j]表示取第i个数时分成了j块
要么是将第i个数加入j块中的最后一块，要么是自成一块,加上前面j-1块的和
状态转移方程：
dp[i][j]=max(dp[i-1][j]+a[i]，max{dp[0][j-1]...dp[i-1][j-1]})
枚举时j为外层循环，i为内层循环，
用滚动数组压缩j,再记录上一轮的dp[0..i][j]的最大值即可
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
int dp[maxn],pre[maxn],a[maxn],m,n;
int main(){
while(scanf(
"%d%d",&m,&n)==
2){
memset(dp,0,
sizeof dp);
memset(pre,0,
sizeof pre);
for(
int i=
1;i<=n;i++)scanf(
"%d",&
a[i]);
int Max;
for(
int j=
1;j<=m;j++
){
Max=-
0x7fffffff;
//用来维护本层的最大值
for(
int i=j;i<=n;i++
){
dp[i]=a[i]+max(dp[i-
1],pre[i-
1]);
//要么加入原有的j组，要么新开一组
pre[i-
1]=Max;
//上一轮的i-1在用过之后才能更新
Max=max(Max,dp[i]);
//把当前的dp[i]更新进Max
}
}
int ans=-
0x7fffffff;
for(
int i=m;i<=n;i++
)
ans=
max(ans,dp[i]);
printf("%d\n",ans);
}
return 0;
}
转载于:https://www.cnblogs.com/zsben991126/p/10279078.html
