分治算法-连续最大子序列和问题
程序员文章站
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))
上一篇: 最大子序列和
下一篇: nginx yii2 配置