分治算法-连续最大子序列和问题

概述

最大连续子序列和问题：
给定k个整数的序列{N1,N2,…,Nk }，其任意连续子序列可表示为{ Ni, Ni+1, …, Nj }，其中 1 <= i <= j <= k。最大连续子序列是所有连续子序中元素和最大的一个。
这个问题的求解思路有很多，可以暴力求解时间复杂度O(N³)，也可以使用动态规划求解时间复杂度O(N)，下面的代码是采用的分治递归求解的时间复杂度O(NlogN)。

代码

def GetCrossSumMax(myList,lowNum,highNum):
    mid=int((lowNum+highNum)/2)
    i=mid
    j=mid+1
    lowSum=myList[i]
    highSum=myList[j]
    TempSum=0
    while i>=lowNum:
        TempSum+=myList[i]
        if TempSum>lowSum:
            lowSum=TempSum
        i-=1
    TempSum=0
    while j<=highNum:
       
        TempSum+=myList[j]
        if TempSum>highSum:
            highSum=TempSum
        j+=1
    return highSum+lowSum
def FindMaxList(myList,lowNum,highNum):
    if(lowNum==highNum):
        return myList[lowNum]
    mid=int((lowNum+highNum)/2)
    low=FindMaxList(myList,lowNum,mid)
    high=FindMaxList(myList,mid+1,highNum)
    cross=GetCrossSumMax(myList,lowNum,highNum)
    return max(low,high,cross)

if __name__=="__main__":
    TestList=[-2,1,-3,4,-1,2,1,-5,4]
    print(FindMaxList(TestList,0,len(TestList)-1))