算法導論，線性時間，最大子數組和。
這個思想，必須先要理解清楚，而后才能 寫代碼 。
參考資料，感謝作者。
https://www.cnblogs.com/jimmy1989/p/8476916.html
感謝您，希望您同意我引用。
這個頁面上，是c 的代碼，，我直接 修改了一點，變成 python 。
并在 https://www.tutorialspoint.com/execute_python_online.php 測試了。
感謝此網站。
def maxSubArray( array):
length = len(array)
boundry = array[0]
print ( 'bound-1--'+str(boundry))
maxArray = array[0]
print ( 'maxArray-1--'+str(maxArray))
#for(i in i<length):
for i in range(1, length):
print '===============================>>>'+str(i)+'>>>go'
if( boundry+array[i] >= array[i] ):
boundry += array[i]
print 'intoif-1=='+ str(boundry)
else:
boundry = array[i]
print 'into-else-1=='+ str(boundry)
if( maxArray < boundry ):
maxArray = boundry
print 'into-ifmax-1=='+ str(maxArray)
return maxArray
a=[13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7,-99,88]
print maxSubArray(a)
運行結果
$python main.py
bound-1--13
maxArray-1--13
===============================>>>1>>>go
intoif-1==10
===============================>>>2>>>go
intoif-1==-15
===============================>>>3>>>go
into-else-1==20
into-ifmax-1==20
===============================>>>4>>>go
intoif-1==17
===============================>>>5>>>go
intoif-1==1
===============================>>>6>>>go
intoif-1==-22
===============================>>>7>>>go
into-else-1==18
===============================>>>8>>>go
intoif-1==38
into-ifmax-1==38
===============================>>>9>>>go
intoif-1==31
===============================>>>10>>>go
intoif-1==43
into-ifmax-1==43
===============================>>>11>>>go
intoif-1==38
===============================>>>12>>>go
intoif-1==16
===============================>>>13>>>go
intoif-1==31
===============================>>>14>>>go
intoif-1==27
===============================>>>15>>>go
intoif-1==34
===============================>>>16>>>go
intoif-1==-65
===============================>>>17>>>go
into-else-1==88
into-ifmax-1==88
88
下面是引用 ， 希望作者同意。
思路詳解
解題思路來源于算法導論習題4.1-5
使用如下思想為最大子數組問題設計一個非遞歸的、線性時間的算法。從數組的左邊界開始，從左至右處理，記錄到目前為止已經處理過的最大子數組。若已知A[1..j]的最大子數組，基于如下性質將解擴展為A[1..j+1]的最大子數組：A[1..j+1]的最大子數組要么是A[1..j]的最大子數組，要么是某個子數組A[i..j+1] (1≤i≤j+1)。在已知A[1..j]的最大子數組的情況下，可以在線性時間內找出形如A[i..j+1]的最大子數組。
注意：本文只討論最大子數組的和的問題，所以后文提到最大子數組時，都是指最大子數組的和。
為了與習題里面敘述保持一致，本節(jié)討論思路時下標都從1開始，A[1]表示第一個元素。
已知 A[1..1] 的最大子數組是第一個元素，要么 A[1..2] 的最大子數組要么是 A[1..1] 的最大子數組，要么是 A[i..2] 的最大子數組。換個說法就是 A[1..2] 的最大子數組要么包含第二個元素，要么不包含第二個元素；所以①需要從包含第二個元素和不包含第二個元素的兩種情況里面選一個最大的值出來。
不包含第二個元素的值是可以確定的，就是 A[1..1] 的最大子數組，是已知的；為了方便起見，稱之為前最大子數組。而包含第二個元素的最大子數組需要另外去算；為了方便起見，我們稱之為邊界最大子數組。我們真正需要的最大子數組就是 前最大子數組 和邊界最大子數組中值較大的一個。
那么如何計算邊界最大子數組？既然這種情況下已經確定了包含第二個元素，②那么我們只需分兩種情況：只包含第二個元素，和不只包含第二個元素；同樣取這兩種情況的最大值。只包含第二個元素的情況是非常簡單的，邊界最大子數組就只是A[2]的值；不只包含第二個元素的情況也簡單，不只包含第二個元素，那么必定包含它的前一個元素，即第一個元素，所以我們需要它的前一個元素的邊界最大子數組。之后A[2]的邊界最大子數組就是這兩種情況的最大值。
也就是說，要確定第A[1..2]的最大子數組，唯一另外需要的元素就是第一個元素的邊界最大子數組。
現在情況清晰了，當計算A[1..2]的最大子數組是，需要的值分別有：前最大子數組（已知）、A[2]的值（已知）、前一個元素的邊界最大子數組。
很明顯這是一個從頭開始，可以迭代求解的問題，迭代的每一步都只需要上一段中加粗的三個值；每一步都為下一步的計算提供了基礎的值。這是一個線性的高效算法。
--- 這些話。理解，可能不容易。我畫了個思維導圖
這個題，算法導論，習題4.1-5
正好是吳軍，吳軍，吳軍老師說的，
我們先從用遞歸來分析問題，把問題，縮小。（假設，很重要）
而后用遞推來解決問題。
請大家一定要記住，采用遞推，每次迭代后的值，記錄下來，下一次迭代時，正好用上。
而遞歸，是在棧 這個數據結構上，去實現的。
基于這兩天的學習，看到分治算法雖好，但有線性時間的，更好的算法。
