题意是要在一段数列中求 m 段互不重合的子数列的最大和。
动态规划，用数组 num[ ] 存储所给数列，建二维数组 dp[ ][ ] ， dp[ i ][ j ] 表示当选择了第 j 个数字( num [ j ] )时，前 j 个数字被分成 i 组的所得最大和。
那么这个最大和等于 max{ ( 前 i - 1 组的和 + 第 i 组(含num[ j - 1]) + num[ j ] )，( 前 i - 1 组的和 + num[ j ] ) }；
即 dp[ i ][ j ] = max( dp[ i ][ j - 1], dp[ i - 1 ][ k ] ) + num[ j ]；
但是这么大的二维数组开不了的，而且每次算当前状态时只需要前一状态，再之前的没什么用，（即状态具有后无效性，前面的选择不会影响后续选择）因此使用滚动数组，再干脆直接开两个一维数组，dp[ ] 和 pre[ ]，pre[ j - 1 ] 表示 j - 1 之前的数的最大和
( 不包括 num[ j - 1 ] ) ，dp[ j ] 表示选择了 num[ j ] 时前 j 个数字的最大和，
则 dp[ j ] = max( dp[ j - 1 ] ，pre[ j - 1 ] ) + num [ j ]；
#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
int dp[maxn],pre[maxn],num[maxn];
int main()
{
int n,m,tmp;
while(~scanf("%d%d",&m,&n))
{
for(int i = ; i <= n; ++i)
scanf("%d",&num[i]);
memset(dp,,sizeof(dp));
memset(pre,,sizeof(pre));
for(int i = ; i <= m; ++i)
{
tmp = -;
for(int k = i; k <= n; ++k)
{
dp[k] = max(dp[k-],pre[k-]) + num[k];
pre[k-] = tmp;
tmp = max(tmp,dp[k]);
}
}
printf("%d\n",tmp);
}
return ;
}