2018-05-24

算法导论，分治算法，最大子数组问题。
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]

向下一山头 进发。