13.Maximum Subarray
動態規劃
使用動態規劃需要的前提：最優子結構性質。
最優子結構性質：
重疊子問題：
用遞歸算法自頂向下解此問題時，每次產生的子問題並不總是新問題，有些子問題被反覆計算。
對每個子問題只解一次， 然後將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數時間查看一下結果。
通常子問題個數隨問題的大小呈多項式增長，因此，用動態規划算法通常只需要多項式時間。
動態規劃步驟：
題目
發現這個問題可以用動態規劃求解：
最優子結構性質
假設數組A的最大子序和對應一個連續元素組成的數組B。那麼數組B的子數組的最大子序和也一定是B的一個連續小部分C。
反證法：如果B的子數組的最大子序不是C，也就是比C的累加和更大，那麼把這段替換到B中，就可能產生更大的值，那麼B就不是A的最大子序和對應的數組，與假設矛盾。故假上述結論正確。
換句話說上面的結論，在求最大子序和的時候，每加入一個新的A[i]都應該使得總的子序和比單獨一個A[i]大才對，否則考慮從A[i]開始尋找新的子段和。當然最終取所有子段和的最大值為最終值。
文字思想：
假設當前數組為A。假設當前最大子段和為b，初值為A[0]。
通過我們上面分析的最優子結構性質可知：每加入一個新的A[i]都應該使得總的子序和比單獨一個A[i]大才對，否則考慮從A[i]開始尋找新的子段和。當然最終取所有子段和的最大值為最終值。
例子：
待處理數組：-2, 1, -3, 4, -1, 2, 1, -5, 4,
初始化前一個子段和為:0
初始化當前進度下最大子段和為第一個元素的值:-2
前一個子段和為:0
如果加入當前元素-2之後的子段和為:-2
因為加入-2之後整個子段和為-2,不如單獨一個當前元素-2大，所以不如從-2開始向後再擴展新的子段和更大
當前新的子段和為:-2
歷史最大的子段和為:-2
更新歷史最大子段和為:-2
前一個子段和為:-2
如果加入當前元素1之後的子段和為:-1
因為加入1之後整個子段和為-1,不如單獨一個當前元素1大，所以不如從1開始向後再擴展新的子段和更大
當前新的子段和為:1
歷史最大的子段和為:-2
更新歷史最大子段和為:1
前一個子段和為:1
如果加入當前元素-3之後的子段和為:-2
因為加入-3之後整個子段和為-2,比單獨一個當前元素-3大，所以擴充-3到上一個子段的尾部
當前新的子段和為:-2
歷史最大的子段和為:1
不更新歷史最大子段和
前一個子段和為:-2
如果加入當前元素4之後的子段和為:2
因為加入4之後整個子段和為2,不如單獨一個當前元素4大，所以不如從4開始向後再擴展新的子段和更大
當前新的子段和為:4
歷史最大的子段和為:1
更新歷史最大子段和為:4
前一個子段和為:4
如果加入當前元素-1之後的子段和為:3
因為加入-1之後整個子段和為3,比單獨一個當前元素-1大，所以擴充-1到上一個子段的尾部
當前新的子段和為:3
歷史最大的子段和為:4
不更新歷史最大子段和
前一個子段和為:3
如果加入當前元素2之後的子段和為:5
因為加入2之後整個子段和為5,比單獨一個當前元素2大，所以擴充2到上一個子段的尾部
當前新的子段和為:5
歷史最大的子段和為:4
更新歷史最大子段和為:5
前一個子段和為:5
如果加入當前元素1之後的子段和為:6
因為加入1之後整個子段和為6,比單獨一個當前元素1大，所以擴充1到上一個子段的尾部
當前新的子段和為:6
歷史最大的子段和為:5
更新歷史最大子段和為:6
前一個子段和為:6
如果加入當前元素-5之後的子段和為:1
因為加入-5之後整個子段和為1,比單獨一個當前元素-5大，所以擴充-5到上一個子段的尾部
當前新的子段和為:1
歷史最大的子段和為:6
不更新歷史最大子段和
前一個子段和為:1
如果加入當前元素4之後的子段和為:5
因為加入4之後整個子段和為5,比單獨一個當前元素4大，所以擴充4到上一個子段的尾部
當前新的子段和為:5
歷史最大的子段和為:6
不更新歷史最大子段和
最終最大子段和為：6
代碼：
複雜度：
時間複雜度：O(nums.length)，遍歷一次數組。空間複雜度：O(1)。
積累：
動態規劃方法的前提，也就是如何看出來這道題可以使用動態規劃。
動態規劃求解步驟，最優值、最優解。
其它：
本題還有許多方法，比如：暴力窮舉、貪心算法、分治算法等。
回顧一下數據結構知識點課程中講的哪些算法其實就是用動態規劃在求解。
可以嘗試求解一下本題最優解。