题目意思：
本题的大致意思为给定一个数组，求其分成m个不相交子段和最大值的问题
参考：https://www.cnblogs.com/kuangbin/archive/2011/08/04/2127085.html
状态dp[i][j]
有前j个数，组成i组的和的最大值。
决策： 第j个数，是在第包含在第i组里面，还是自己独立成组。
方程 dp[i][j]=Max(dp[i][j-1]+a[j] , max( dp[i-1][k] ) + a[j] ) 0<k<j
空间复杂度，m未知，n<=1000000， 继续滚动数组。
时间复杂度 n^3. n<=1000000. 显然会超时，继续优化。
max( dp[i-1][k] ) 就是上一组 0…j-1 的最大值。我们可以在每次计算dp[i][j]的时候记录下前j个
的最大值 用数组保存下来 下次计算的时候可以用，这样时间复杂度为 n^2.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 1000010, INF = 0x7fffff;
int n, m;
int a[MaxN];
int dp[MaxN]; //dp[i] 表示前i个数，若干不相交子段和的最大值
int mmax[MaxN]; //mmax[i] 表示数组 dp 从 dp[0] 到 dp[i] 的最大值void solve()
{
dp[0] = 0, mmax[0] = 0; int i, j, mmmax;for(i = 1; i <= m; ++i){
mmmax = -INF;for(j = i; j <= n; ++j){
dp[j] = max(dp[j - 1] + a[j], mmax[j - 1] + a[j]);mmax[j - 1] = mmmax;mmmax = max(mmmax, dp[j]);}}printf("%d\n", mmmax);
}int main()
{
while(scanf("%d%d", &m, &n) != EOF){
for(int i = 1; i <= n; ++i){
scanf("%d", &a[i]);mmax[i] = 0, dp[i] = 0;}solve();}return 0;
}/* 1 3 1 2 3 2 6 -1 4 -2 3 -2 3 *//* 6 8 */