我如何使用分而治之的方法解决FindMaximumSubarray的重复错误？

Question

这是我对findMaximumSubarray的解决方案，我遵循CLRS伪代码算法，但遇到此递归错误，我试图找出原因，但是却什么也没得到！

我无法理解递归的这一部分，第一行是找到左除数数组，直到到达一个元素的基本情况为止，然后我的大脑在发抖，我无法想象之后会发生什么！

 leftLow, leftHigh, leftSum = FindMaxSubarray(array, low, mid)
 rightLow, rightHigh, rightSum = FindMaxSubarray(array, mid, high)
 crossLow, crossHigh, crossSum = MaxCrossSubarray(array, low, mid, high)

这是整个代码。

array = [0,1,-2,3,4,-2, 5, -1, 10, -2 ,11,9, -5, -10, 12]
low = 0 
high = len(array)

mid  = len(array)//2


def MaxCrossSubarray(array, low, mid, high):
    sum = 0
    left_sum = float('-inf')
    for i in range(mid, low, -1):
        sum = sum+array[i]
        if sum > left_sum:
            left_sum = sum 
            max_left = i
    right_sum = float('-inf')
    sum = 0
    for i in range(mid+1, high):
        sum = sum+array[i]
        if sum > right_sum:
            right_sum = sum 
            max_right = i
    return (max_left, max_right, left_sum+right_sum)

def FindMaxSubarray(array, low, high):
    if high == low :
        return (low, high, array[low])
    else:
        mid = (high+low)//2 
        leftLow, leftHigh, leftSum = FindMaxSubarray(array, low, mid)
        rightLow, rightHigh, rightSum = FindMaxSubarray(array, mid, high)
        crossLow, crossHigh, crossSum = MaxCrossSubarray(array, low, mid, high)
        if leftSum >= rightSum and leftSum >=crossSum:
            return (leftLow, leftHigh, leftSum)
        elif rightSum >= leftSum and rightSum >=crossSum:
            return (rightLow, rightHigh, rightSum)
        else:
            return (crossLow, crossHigh, crossSum)

low, high, sum = FindMaxSubarray (array, low, high)        

Answer 1

 leftLow, leftHigh, leftSum = FindMaxSubarray(array, low, mid)
 rightLow, rightHigh, rightSum = FindMaxSubarray(array, mid, high)
 crossLow, crossHigh, crossSum = MaxCrossSubarray(array, low, mid, high)

上面代码中的想法是，您将在数组的右，左和交叉和处找到子数组的最大值。正如您在问题the first line is to find divide left array until reaching the base case which is one element中所解释的。这是正确的，其他部分也适用相同的逻辑。

递归问题源于此行

rightLow, rightHigh, rightSum = FindMaxSubarray(array, mid, high)

mid=0和high = 1会导致递归错误，因为在这些值下，以下内容始终为假。

if high == low :
    return (low, high, array[low])

要解决递归问题，只需更改为此

rightLow, rightHigh, rightSum = FindMaxSubarray(array, mid+1, high)

这确保可以满足返回条件，从而防止了递归错误。

已更改，似乎您的MaxCrossSubArray在逻辑上不正确，并且在运行它时出现以下错误

UnboundLocalError：分配前引用了本地变量'max_right'

调查并查看是否可以解决。

N.B：已知CLRS包含一些错误，并且相对较旧。因此，我建议您不要坚持使用相同的解决方案，而要寻找其他可能性。例如，请参见this。