算法导论，线性时间，最大子数组和。
这个思想，必须先要理解清楚，而后才能 写代码 。
参考资料，感谢作者。
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]的最大子数组。
注意：本文只讨论最大子数组的和的问题，所以后文提到最大子数组时，都是指最大子数组的和。
为了与习题里面叙述保持一致，本节讨论思路时下标都从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
正好是吴军，吴军，吴军老师说的，
我们先从用递归来分析问题，把问题，缩小。（假设，很重要）
而后用递推来解决问题。
请大家一定要记住，采用递推，每次迭代后的值，记录下来，下一次迭代时，正好用上。
而递归，是在栈 这个数据结构上，去实现的。
基于这两天的学习，看到分治算法虽好，但有线性时间的，更好的算法。
