经典的dp问题，但自己的dp 水平实在太差。
首先定义，dp[i][j]表示把前 j 个数分成 i 组的最大值,可以得到状态转移方程：
dp[i][j] =max (dp[i][j-1]+s[j],max(dp[i-1][k]+a[j])) （0<=k<=j-1）
前面表示s[j]独立成组，后面表示把s[j]加入到前面的组中。
此时时间复杂度为O(mnn),对于本题的数据肯定tle，因此需要优化。
通过状态转移方程可以发现dp[i][j]只与dp[i][j-1]和dp[i-1]的私有状态有关。即当dp 只与上一个状态去有关时，我们都可以记录去前面的最优解，然后优化掉一个n。如当我们记录下dp[i-1]的最大值，就不必去遍历k。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e6+5;
int n,m;
int s[N];
int dp[N],mx[N];
int main()
{
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&s[i]);
        dp[1]=0;
        memset(mx,0,sizeof(mx));
        int x=0;
        for(int i=1;i<=m;i++)
        {
            x=-0x3f3f3f3f;
            for(int j=i;j<=n;j++)//因为取m段，故最早取也是从i 开始
            {
                dp[j]=max(dp[j-1]+s[j],mx[j-1]+s[j]);
                mx[j-1]=x;
                x=max(x,dp[j]);
            }
        }
        printf("%d\n",x);
    }
    return 0;
}