（轉）動态規劃 - 最大子數組和（最大子序列和 | 連續子數組最大和）

原文作者：Yx.Ac   文章來源：勇幸|Thinking (http://www.ahathinking.com)  

DP方案

考慮DP求解。這個問題可以繼續像LCS、LIS一樣，“從後向前”分析（《程式設計之美》對此又是從前向後分析的，個人不太習慣）。我們考慮最後一個元素arr[n-1]與最大子數組的關系，有如下三種情況：

1. arr[n-1]單獨構成最大子數組
2. 最大子數組以arr[n-1]結尾
3. 最大子數組跟arr[n-1]沒關系，最大子數組在arr[0-n-2]範圍内，轉為考慮元素arr[n-2]

從上面我們可以看出，問題分解成了三個子問題，最大子數組就是這三個子問題的最大值，現假設：

1. 以arr[n-1]為結尾的最大子數組和為End[n-1]
2. 在[0-n-1]範圍内的最大子數組和為All[n-1]

如果最大子數組跟最後一個元素無關，即最大和為All[n-2]（存在範圍為[0-n-2]），則解All[n-1]為三種情況的最大值，即All[n-1] = max{ arr[n-1]，End[n-1]，All[n-2] }。從後向前考慮，初始化的情況分别為arr[0]，以arr[0]結尾，即End[0] = arr[0]，最大和範圍在[0,0]之内，即All[0]=arr[0]。根據上面分析，給出狀态方程：

1 All[i] = max{ arr[i]，End[i-1]+arr[i]，All[i-1] }      

代碼如下：

1 /* DP base version*/
 2 #define max(a,b) ( a > b ? a : b)
 3  
 4 int Maxsum_dp(int * arr, int size)
 5 {
 6     int End[30] = {-INF};
 7     int All[30] = {-INF};
 8     End[0] = All[0] = arr[0];
 9  
10     for(int i = 1; i < size; ++i)
11     {
12         End[i] = max(End[i-1]+arr[i],arr[i]);
13         All[i] = max(End[i],All[i-1]);
14     }
15     return All[size-1];
16 }      

上述代碼在空間上是可以優化為O(1)的，這裡就不說了，詳參考《程式設計之美》2.14。

下面說一下由DP而導出的另一種O(N)的實作方式，該方法直覺明了，個人比較喜歡，是以後續問題的求解也是基于這種實作方式來的。

仔細看上面DP方案的代碼，End[i] = max{arr[i]，End[i-1]+arr[i]}，如果End[i-1]<0，那麼End[i]=arr[i]，什麼意思？End[i]表示以i元素為結尾的子數組和，如果某一位置使得它小于0了，那麼就自目前的arr[i]從新開始，且End[i]最初是從arr[0]開始累加的，是以這可以啟示我們：我們隻需從頭周遊數組元素，并累加求和，如果和小于0了就自目前元素從新開始，否則就一直累加，取其中的最大值便求得解。

到這裡其實就可以了，在《程式設計之美》中，作者故意沒有按照這種推導來實作（我猜的），而是在End[i-1]<0時，讓End[i]=0，進而留出了一個問題（元素全是負數怎麼辦），其實如果按照上面的推導直接實作的話，就不存在這個問題了；（題外話：還是要堅持寫部落格做總結，這是一個重新思考的過程，這幾天做這幾道題發現當時也就看懂大部分，更多的細節和問題是在寫部落格重新整理的過程中發現的。後面擴充問題也是在整理過程中才發現了《程式設計之美》中的錯誤。）

基于上面的推導，代碼如下：

1 /* DP ultimate version */
 2 int Maxsum_ultimate(int * arr, int size)
 3 {
 4     int maxSum = -INF;
 5     int sum = 0;
 6     for(int i = 0; i < size; ++i)
 7     {
 8         if(sum < 0)
 9         {
10             sum = arr[i];
11         }else
12         {
13             sum += arr[i];
14         }
15         if(sum > maxSum)
16         {
17             maxSum = sum;
18         }
19     }
20     return maxSum;
21 }      

其實上面的方法雖說是從DP推導出來的，但是寫完發現也是很直覺的方法，求最大和，那就一直累加呗，隻要大于0，就說明目前的“和”可以繼續增大，如果小于0了，說明“之前的最大和”已經不可能繼續增大了，就從新開始，如此這樣。

此題還有擴充，數組可以首位相連

轉載于:https://www.cnblogs.com/haoyancoder/p/3362211.html