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;
  }
}