弱弱上路，看了好多题解。。。。【A的】

题意就是求最大m子段和。

我们先用a[1e6+7]存入数据；

定义：DP[ i , j ] 为前 j 个元素的 i 个子段的最大和，且第 i 个子段中包含了元素 a[j]。

我们先来看：DP[ i , j ]状态方程由来；

对于一个元素 a[ j ] ：

① 他可以自成一段；

②也可以包含第 i 段上，而且是第 i 段上的末尾元素；

那么：

对于①：DP[ i , j ]=max(DP[ i - 1 ,t ])+a[ j ]; t∈（ i - 1 , j ）;

我把元素a[ j ]自成一段，我们的目的是要达到DP[ i , j ]最大，那么就是要使前面的 i - 1 段最大，所以需要找一下最大，而且第 i - 1 段中的末尾元素肯定是区间（i - 1 , j）上；

对于②：DP[ i , j ]=DP[ i , j - 1 ] + a[ j ];

其实一开始，我是不理解为什么就是DP[ i , j - 1 ]啊，为什么不可以是DP[ i , j - 2 ],DP[ i , j - 3 ]，然后再举例子就真是自己sb了(T . T)，因为前提是子段，是连续的！！然后现在我们的条件是元素a[ j ]在第 i 段上了，而且是该段上的最后一个元素；

那么就好了啊，已经搞好了；

=> DP[i,j]=max(max(DP[ i - 1 , t ] ) ,DP[ i , j - 1 ] )+a[ j ];

但是这样写，会发现。。。哇艹，他的n是1e6啊！！！你给我开个二维数组那样代表？这样是不行的；

我们可以看到DP[ i , j ] 的值只和 DP[ i , j - 1 ] 和DP[ i - 1 , t ] 这两个值相关，

因此不需要二维数组，可以用滚动数组，只需要两个一维数组，

用now[ j ] 表示现阶段的最大值，即 DP[ i , j − 1] + a[ j ]

用pre[ j ] 表示上阶段的最大值，即 max{DP[ i − 1,t ] )+ a[ j ]

代码：

#include<iostream>

#include<cstdio>

#include<math.h>

#include<queue>

#include<map>

#include<stdlib.h>

#include<string>

#include<string.h>

#include<algorithm>

using namespace std;

typedef long long LL;

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

const int N=1e6+7;

int a[N];

int pre[N];

int now[N];

int Max_duan(int m,int n)

{

    int i,j,max_sum;

    memset(pre,0,sizeof(pre));

    memset(now,0,sizeof(now));

    for(i=1;i<=m;i++){

        max_sum=INT_MIN;

        for(j=i;j<=n;j++){

            now[j]=max(pre[j-1],now[j-1])+a[j];

            pre[j-1]=max_sum;

            if(max_sum<now[j])

                max_sum=now[j];

        }

        pre[j-1]=max_sum;

    }

    return max_sum;

}

int main()

{

    int n,m;

    while(~scanf("%d%d",&m,&n))

    {

        for(int i=1;i<=n;i++)

            scanf("%d",&a[i]);

        printf("%d\n",Max_duan(m,n));

    }

    return 0;

}