题意：从一个序列中选出分成不交叉的m段 的最大和
解析 ： 题目中 1 <= n <=1000000 所以二维数组是不能用了 所以 要想到简化为一维
dp[i][j]表示以i结尾的前i个数 分成j组的最大和 对于一个数A[i] 我们有两种选择，一是与第（i-1）个数在一组 或者 自成一组 ，所以状态方程就出来了
dp[i][j] = max(dp[i-1][j], max(dp[k][j-1] {k| 1<= k <= i-1} ))+A[i];
max(dp[k][j-1] {k| 1<= k <= i-1})表示前i-1个数组成的j-1组的最大值
这道题没有说m是多少 所以比较尴尬。。。 又因为每个状态只与它一个状态有关，那么就用滚动数组好了
maxx = max(maxx, dp[k^1][i-1]); // 前（i-1）个 分成（k-1）组的最优解
异或^是相同为0，不同为1，可以用^1来转换状态
dp[k][i] = max(dp[k][i-1], maxx) + A[i];
滚动数组讲解：https://www.cnblogs.com/WTSRUVF/p/9210633.html
具体详情见代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn =, INF = 0x7fffffff;
int A[maxn], dp[][maxn];
int main()
{
int m, n;
while(~scanf("%d%d",&m,&n))
{
mem(dp,);
mem(A,);
int k =; // 初始化为0
for(int i=; i<=n; i++)
scanf("%d",&A[i]);
int maxx, ret;
for(int j=; j<=m; j++)
{
k ^=; //因为只与j和j-1两个状态有关 所以每次都要异或
maxx = dp[k^][j-]; //maxx的意义为 前j-1个数 分成k-1组的最优解 又第j组最小是j个数 所以每次的maxx开始值为 dp[j-1][j-1] 即 dp[k^1][j-1]
dp[k][j] = dp[k^][j-] + A[j]; // 因为选择第i个数，分成i段，所以只能自己成一段,那么只能这样写;
ret = dp[k][j]; //ret 为这些数分成k组后最大的值 开始值为dp[k][j];
for(int i=j+; i<=n; i++)
{
maxx = max(maxx, dp[k^][i-]);
dp[k][i] = max(dp[k][i-], maxx) + A[i];
ret = max(ret, dp[k][i]);
}
}
printf("%d\n",ret); } return;
}