Как я решаю ошибку повторения FindMaximumSubarray, используя подход разделяй и властвуй? - PullRequest
Новая
       105

Как я решаю ошибку повторения FindMaximumSubarray, используя подход разделяй и властвуй?

1 голос
/ 14 апреля 2020

Это мое решение найти MaximumSubarray, я следую алгоритму псевдокода 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)

1 Ответ

1 голос
/ 14 апреля 2020 
 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. Это верно, и тот же лог c применяется к другим частям.

Эта проблема возникает из-за рекурсивной проблемы 

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' перед назначением

Просмотрите и посмотрите, можете ли вы ее решить.

NB: Известно, что CLRS содержит некоторые ошибки, и это относительно старый Поэтому я бы посоветовал вам не придерживаться того же решения, но искать другие возможности. См. Например this .

...