弱弱上路，看了好多题解。。。。【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
     
      #include
      
       #include
       
        #include
        
         #include