HDU1024-最大子段和

1.​​题目链接​​。题意大概就是，把一个数组划分成不相交的m段，使得这m段之和加起来最大。输出最大值。这一看肯定是个DP了，我么稍微的分析一下其实就可以写出DP式子。

2.dp[i][j]表示前j个数划分成i段的最大值，显然我们这里的决策取决于j是否属于第i段。那么就会有两种情况（1）第j个元素被划分在了第i段，这个转移就很简单了dp[i][j]=d[i][j-1]+a[j].这个转移应该是很显而易见的吧。就不多说了。那么第二种情况呢？（2）第j个元素没有被划分在第i段内，那么这里就有点难以理解了。既然第j个元素没有被划分在第i段内，说明前j-1个元素被划分成了i-1段。那么这里就有一个问题，被划分成i-1段至少需要i-1个元素，最多j-1个元素。（因为当前只有j-1个元素可用）。所以这里并不是简单的dp[i][j]=dp[i-1][j-1]+a[j],需要枚举从i-1开始，到j-1结束这些状态，到底多少个元素划分成i-1段是最大的。所以这里的dp式子应该是这样写：dp[i][j]=max(dp[i-1][k]+a[j])&&i-1<=k<=j-1.综合起来的DP式就是这样的：

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

看上去这题已经结束了，然而一看数据范围就知道凉凉。m的范围没有给，n是1e6.这个DP时间复杂度是n3方，空间只要是m大一点点就爆内存。所以，这个式子没用。要找到优化的方法。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e6+10;
int dp1[maxn];//这个记录当前的最大值
int a[maxn];//数据存放的地方
int dp2[maxn];//这个记录上一个的最大值
int tem = 0;
const int INF = 1e9;
#pragma warning(disable:4996)
int main()
{
  int n, m;
  while (~scanf("%d%d", &m, &n))
  {
    for (int i = 1; i <= n; i++)
    {
      scanf("%d", &a[i]);
      dp1[i] = 0;
      dp2[i] = 0;
    }
    //初始化
    for (int i = 1; i <= m; i++)
    {
      tem = -INF;
      for (int j = i; j <= n; j++)
      {
        dp1[j] = max(dp1[j - 1] + a[j], dp2[j - 1] + a[j]);
        dp2[j - 1] = tem;
        tem = max(tem, dp1[j]);
      }
    }
    cout << tem << endl;
  }
}