如何使用分治法解决 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)

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

更改后，您的 MaxCrossSubArray 似乎在逻辑上不正确，并在运行上给出以下错误

UnboundLocalError: local variable 'max_right' referenced before assignment

看看能不能解决

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

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

How I solve the recurrence error of FindMaximumSubarray using divide and conquer approach?

python

algorithm

divide-and-conquer

clrs