python算法之分治算法（连续子列表的最大和）_分治算法 最大连续子段 python

连续子列表的最大和

在一个列表中找到连续子列表的最大和。列表中的数字可负可正，并且子列表不能为空。

问题提出：

找到以下列表的最大子列表的和：
[-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))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26