欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-08 19:22:36
...

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

概述

最大连续子序列和问题:
给定k个整数的序列{N1,N2,…,Nk },其任意连续子序列可表示为{ Ni, Ni+1, …, Nj },其中 1 <= i <= j <= k。最大连续子序列是所有连续子序中元素和最大的一个。
这个问题的求解思路有很多,可以暴力求解时间复杂度O(N3),也可以使用动态规划求解时间复杂度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))