思路：
最开始是真的没什么思路，看别人的摸懂的。
dp[i][j] 表示前j个数分成i段所能得到的最大值，并且第i段包括了第j个那个元素即a[j]，a数组表示原存放数的数组
dp[i][j] 有两种情况可以得到它，
第一：和第j个元素一起放在第i段的末尾，即dp[i][j-1] + a[j]，这样可以得到一个dp[i][j]
第二：第j个元素单独成为一段，那么就要和前面前j-1个元素分成i-1段所能得到的最大值相加，然后组成一个dp[i][j],即max(dp[i-1[k]+a[j]) (0<k<j)
以上为这个dp思路的精华所在，最后一个元素独成一段是最重要的一点，因为每一个不独成一段的元素都被第一点包含进去了，即第一点是由独成一段开始然后才会有很长的一段的，所以此dp思路成立。
状态转移方程为：
dp[i][j] = max(dp[i][j-1] + a[j], max(dp[i-1][k] + a[j])) (0<k<j)
for( i = 1; i <= m; ++i){
for( j = i; j <= n; ++j){
dp[j] = dp[j-1] + a[j];
for(int r = 1; r < j; ++r){
dp[j] = max(dp[j],dp[r] + a[j]);
}
}
}
这样看上去差不多问题得到解决了，思路正确，代码应该是没问题的。
可是题目的j会达到很大，一百万级别，那么只要i稍微大点，就会MLE，而且也会TLE，因此有必要解决时空的问题。
我们继续来看，
我们每一次循环dp的时候，它的前后关联的元素是哪些，这是简化dp的空间的基本点。
可以发现，只和前面分成i-1段的结果有关，因此我们就有两种方法来简化，
第一种是：保存前后两个状态，这样空间第一维就固定为2了，吃的起，可以
第二种：就是滚动数组了，滚动数组是dp的一个经典缩空间的方法，因为我们每一次都覆盖掉刚用过的数据，那么我们就只要用一维就可以实现了。
到了这里我们解决了空间的问题，可是时间的问题依旧没有得到解决，
我们在max(dp[i-1][k] + a[j]) (0<k<j) 这里还是会花费一个O(n)的时间复杂度去查找，这导致了我们的时间复杂度达到了O(M*N^2)，这是不可忍受的，不能接受的
那么要如何解决这个问题呢，我们从滚动数组的更新上可以发现，我们可以用滚动数组的类似原理，我们开个数组专门存放前k个元素组成i段的元素的最大值
即 mx[i][j] 表示前1-j个元素的组成i段的最大值，即max(dp[i-1][k] + a[j]) (0<k<j) 这个用一个二维数组表示了，
此时我们在对其使用滚动数组，使得其变成一维mx[j]，这样我们就可以同滚动数组的更新一起更新mx的值了。
即用一个mmax保存前 mx[i][j] ，然后用其值更新下一个mx[j]的值，这样就可以缩掉一维。
for( i = 1; i <= m; ++i){
mmax = -INF;
for( j = i; j <= n; ++j){
dp[j] = max(dp[j-1] + a[j], mx[j-1] + a[j]);
mx[j-1] = mmax;
mmax = max(mmax,dp[j]);
}
}
每次更新都更新mx的值。
到此时空都得到了一定的解决了，提交859ms。。。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define eps 10e-8
const int MAX_ = 1000010;
const int N = 100010;
const int INF = 0x7fffffff;
int a[MAX_], mx[MAX_] ,dp[MAX_];
int main(){
int n, m, mmax, i, j;
while(~scanf("%d%d",&m,&n)){
for( i = 1; i <= n; ++i){
scanf("%d",&a[i]);
dp[i] = mx[i] = 0;
}
dp[0] = mx[0] = 0;
for( i = 1; i <= m; ++i){
mmax = -INF;
for( j = i; j <= n; ++j){
/*dp[j] = dp[j-1] + a[j];
for(int r = 1; r < j; ++r){
dp[j] = max(dp[j],dp[r] + a[j]);
}*/
dp[j] = max(dp[j-1] + a[j], mx[j-1] + a[j]);
mx[j-1] = mmax;
mmax = max(mmax,dp[j]);
}
//mx[n] = mmax;
}
printf("%d\n",mmax);
}
return 0;
}