上次完成最大子序和算是對這類算法的入門，現在想要對其進行加深學習。

---

?

　　最大子數組的問題里對我印象最深的就是動態規劃的解決方法——“解其不同部分（即子問題），再根據子問題的解以得出原問題的”。這種解決方法十分常用，而其在一維數組中的總結以及最優解就是Kadane算法。

Kadane算法

//C++偽代碼
int kadane(){int ans = n[0];dp[0] = n[0];for(int i = 1;i < strlen(n);i++){dp[i] = Max(n[i],dp[i-1]+n[i]);ans = Max(dp[i],ans);} }

　　作為最簡潔的算法，我在這里先列上，java形式在之前的隨筆中就有，但發現解釋和我的理解有不一樣的地方，這影響到我對二維數組的理解，所以在此重新學習一遍。

　　首先是關注點。要著重注意：指定數組中某一個元素 n[i] 作為最大子序列的末尾元素時， 能找到的最大子數組的求和值是多少。這樣但我們看第一個元素n[0]的時候，只需要關注其后一個元素即可；而在算子序和的時候，n[i...j]也只需要關注n[j+1]即可。意思就是n[i...j]中的最大子數組只會包含或不包含n[j+1]。如果包含，再看下一個元素。如果不包含，那么從n[j+2]再開始找即可。過程中記錄出現的最大子序和。

?

二維數組中用動態規劃

　　既然問題擴展了一個維度，那就只要找到子問題就還是能用動態規劃。

　　如果簡單的說：將同一列的元素與前一行的元素相加得到一個一維數組，對一維數組進行Kadane算法就能找出最大子數組的和。但這樣只是描述了過程，很難理解（不過對過程進行一次演繹后確實能理解不少，It just work）。

public int kadane2d(int n[][]){int rows = n.length;int cols = n[0].length;int temp[] = new int[rows];int result;//maxSumfor(int left = 0; left < cols ; left++){for(int i=0; i < rows; i++){temp[i] = 0;}for(int right = left; right < cols; right++){for(int i=0; i < rows; i++){temp[i] += n[i][right];}int kadaneResult = kadane(temp);//currentSumif(kadaneResult > result){result = kadaneResult;}}}return result;}

　　時間復雜度近似O（n³）——O（cols*rows*cols）

　　具體過程為Maximum Sum Rectangular Submatrix in Matrix dynamic programming/2D kadane（Youtube）。

?

---

?

　　后記，記下自己的未實現過程。

　　本來想著用遞歸和二分法來解決并節約時間復雜度，但解決時遇到問題，沒法在二分后判斷跨越中間的子數組的大小，所以宣告放棄。但或許什么時候想出來了也不失為一種解決方案。

　　參考網上解題過程后，已經覺得找最大子數組問題是把我引入動態規劃的一道經典例題，所以最后歸納的方案還是用了Kadane算法來解決。

轉載于:https://www.cnblogs.com/limitCM/p/10583311.html

總結

以上是生活随笔為你收集整理的算法问题拓展——kadane算法及其二维数组的扩展的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。