题意：从n个数中选出m段不相交的连续子段，求这个和最大。
分析：经典dp，dp[i][j][0]表示不取第i个数且前i个数分成j段达到的最优值，dp[i][j][1]表示取了第i个数且前i个数分成j段达到的最优值。
那么有：
dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]).
dp[i][j][1]=max(dp[i-1][j-1][0]+a[i],max(dp[i-1][j-1][1],dp[i][j][1])+a[i])).
红色部分略坑，仔细体会一下，因为连续的一段可能拆成多一段刚好符合m段到达最好，不一定得选一段连续的子系列只当成一段最好，可能分成多段更优。
由于n过大，使用滚动数组优化空间。
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 1000010
#define inf 0x3f3f3f3f
using namespace std;
int dp[][N][],a[N];
int n,m;
int main()
{
while(scanf("%d%d",&m,&n)>)
{
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for (int i = ; i <= m; i++) {
dp[][i][] = dp[][i][] = dp[][i][] = dp[][i][] = -inf;
}
dp[][][]=dp[][][]=;
for(int i=,t=;i<=n;i++,t=!t)
{
for(int j=;j<=i&&j<=m;j++)
{
dp[t][j][]=max(dp[!t][j][],dp[!t][j][]);
if(j)dp[t][j][]=max(dp[!t][j-][]+a[i],max(dp[!t][j][],dp[!t][j-][])+a[i]);
}
}
printf("%d\n",max(dp[n&][m][],dp[n&][m][]));
}
}