Несвязанная локальная ошибка в задаче максимального подмассива из алгоритма cormens

Question

Я пытаюсь следовать подходу алгоритма Кормена к решению проблемы подмассива с максимальной суммой, используя динамическое программирование в Python. Для этого я уже создал код подмножества с максимальным пересечением, который работает нормально.

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

Но проблема в основной программе.

def max_subarray(arr, low, high):
if low == high:
    return (low, high, arr[low])
mid = (low+high)//2
left_low, left_high, left_sum = max_subarray(arr, low, mid)
right_low, right_high, right_sum = max_subarray(arr, mid+1, high)
cross_low, cross_high, cross_sum = maxcrosssub(arr, low, mid, high)

if left_sum >= right_sum and left_sum >= cross_sum:
    return(left_low, left_high, left_sum)
elif right_sum >= left_sum and right_sum >= cross_sum:
    return(right_low, right_high, right_sum)
else:
    return(cross_low, cross_high, cross_sum)

Я получаю эту ошибку

UnboundLocalError: local variable 'max_right' referenced before assignment.

Я пытался использовать имя глобальной переменной после некоторых ответов при переполнении стека, но это все еще неза работой.Кто-нибудь может подсказать, что я делаю не так?

Answer 1

Проблема

Проблема возникает из первой функции maxcrosssub, именно из-за того, что в некоторых случаях max_right используется (ссылается) перед инициализацией (присваиванием).Например, если условие sum > left_sum никогда не выполняется.

Решение

Присвойте значение max_right в начале (перед ссылками)

Попробуйте это

Я пытаюсь следовать подходу алгоритма Кормена для решения проблемы подмассива с максимальной суммой, используя динамическое программирование в Python. Для этого я уже создал код подмножества с максимальным пересечением, который работает нормально.

def maxcrosssub(arr, low, mid, high):
    left_sum = float("-inf")
    sum = 0

    # Here is where you can assign a value to 'max_right'
    max_right = 0    # For example

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