算法导论，分治算法，最大子数组问题。
python ，代码抄袭，Dacixie的博客
--
https://blog.csdn.net/Dacixie/article/details/79440014
（尊重作者，如果此处引用，您有意见，请联系我，qq 2466581516）
感谢 在线python 运行环境 ，
https://www.tutorialspoint.com/execute_python_online.php
def MaxCrossSubArray(A,low,mid,high):
LeftMaxSum=A[mid]
leftSum=A[mid]
leftIndex=mid
for i in range(mid-1,low-1,-1):
leftSum=leftSum+A[i]
if leftSum>LeftMaxSum:
LeftMaxSum=leftSum
leftIndex=i
rightMaxSum=0
rightSum=0
rightIndex=mid
for i in range(mid+1,high+1):
rightSum+=A[i]
if rightSum>rightMaxSum:
rightMaxSum=rightSum
rightIndex=i
MaxSum=LeftMaxSum+rightMaxSum
return [MaxSum,leftIndex,rightIndex]
def MaxSubArray(A,low,high):
if low==high:
return [A[low],low,high]
mid=(low+high)//2
Left=MaxSubArray(A,low,mid)
Cross=MaxCrossSubArray(A,low,mid,high)
Right=MaxSubArray(A,mid+1,high)
List=[Left,Cross,Right]
# there is some hard code,,,,,,,,,
result=sorted(List,key = lambda list : list[0],reverse=True)
# only for see the detail ,,print
print result
return result[0]
a=[13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7,-99,88]
print(MaxSubArray(a,0,len(a)-1))
the result
$python main.py
[[13, 0, 0], [13, 0, 0], [-3, 1, 1]]
[[13, 0, 0], [10, 0, 1], [-25, 2, 2]]
[[20, 3, 3], [20, 3, 3], [-3, 4, 4]]
[[20, 3, 3], [13, 0, 0], [5, 0, 3]]
[[-16, 5, 5], [-16, 5, 5], [-23, 6, 6]]
[[38, 7, 8], [20, 8, 8], [18, 7, 7]]
[[38, 7, 8], [15, 6, 8], [-16, 5, 5]]
[[38, 7, 8], [20, 3, 3], [17, 3, 4]]
[[12, 10, 10], [5, 9, 10], [-7, 9, 9]]
[[12, 10, 10], [12, 10, 10], [-5, 11, 11]]
[[15, 13, 13], [-7, 12, 13], [-22, 12, 12]]
[[15, 13, 13], [12, 10, 10], [7, 10, 11]]
[[7, 15, 15], [3, 14, 15], [-4, 14, 14]]
[[88, 17, 17], [-11, 16, 17], [-99, 16, 16]]
[[88, 17, 17], [7, 15, 15], [7, 15, 15]]
[[88, 17, 17], [18, 13, 15], [15, 13, 13]]
[[88, 17, 17], [43, 7, 10], [38, 7, 8]]
[88, 17, 17]
向下一山头 进发。
