连续子列表的最大和
在一个列表中找到连续子列表的最大和。列表中的数字可负可正,并且子列表不能为空。
问题提出:
找到以下列表的最大子列表的和:
[-2,1,-3,4,-1,2,1,-5,4]
解题思路
最大子列表有可能在左子列表、右子列表与右子列表之间。我们需要做的是找到左子列表的最大子列表的和、右子列表的最大子列表的和、左子列表与右子列表之间的子列表的最大和,再进行比较。
三种可能:
如何找到左子列表与右子列表的最大子列表的和呢?
分治的想法是:让左子列表与右子歹表的子列表回答这个问题就可以了,此时此刻不需要知道答案,只需要知道答案只有三种可能。
现在需要做的是找到第三种可能,也就是左子列表与右子列表之间的子列表的最大和。i一个中点,遍历中点左边的值,跟踪记录已遍历过的值的总和,取这些总和的最大值;遍历5点右边的值,跟踪记录已遍历过的值的总和,取这些总和的最大值。最后,左面的最大值加右面的最大值加上中点值就是想要的值。通过上述方法,得到6,也就是4+(-1)+2+1,
现在来找左子列表的最大和。如图所示,对待子列表的方式与对待列表的方式相同,还是有三个可能值,第一个与第二个暂时不关心,让左子列表的子列表解决,找到第三个可能值就可以了,,利用上述方法得到2:(-2)+1+(-3)+4
现在需要找到左子列表的左子列表的最大和。如图所示,第一种可能是-2,第二种可能是1,第三种可能是-1,返回三者的最大值: 1
同理,左子列表的右子列表的返回值是4,如图10.21所示,左子列表的两个子列表返回对应的最大和,之前已经得出第三种可能值,所以现在可以进行比较。三种可能是: 1、4、2,返回三者中的最大值: 4.
以同样的方式对待列表的右子列表,得到第二可能值:4.如图所示,最大值(答案)是6,所以输出是6.
最终代码
def findMaxSum(A): #传入参数,非常关键,否则会报错“超过最大递归深度”
if len(A)<=1:
return A[0]
mid=len(A)//2
leftA=A[:mid]
rightA=A[mid:]
leftMaxSum=findMaxSum(leftA)#递归求左边的最大序列和
leftAfinal = 0#用于包含左边最后一个数的累加求和
#考虑到存在序列全为负数的情况,因为初始化为负无穷而非0
leftAfinalMax = -float('Inf')#包含左边最后一个数的最大序列和
for i in range(0,len(leftA))[::-1]:
leftAfinal=leftAfinal+leftA[i]
if leftAfinal>leftAfinalMax:
leftAfinalMax=leftAfinal
rightMaxSum=findMaxSum(rightA)#递归求右边的最大序列和
rightAfinal = 0#用于包含右边第一个数的累加求和
#考虑到存在序列全为负数的情况,因为初始化为负无穷而非0
rightAfinalMax = -float('Inf')#包含右边第一个数的最大序列和
for j in range(0,len(rightA)):
rightAfinal=rightAfinal+rightA[j]
if rightAfinal>rightAfinalMax:
rightAfinalMax=rightAfinal
crossMaxSum = leftAfinalMax + rightAfinalMax
return max(leftMaxSum, rightMaxSum, crossMaxSum)#返回三个可能的最大值
A=[2,3,4,1,-1,7,-3,7,-6]#实例
print(findMaxSum(A))