Как исправить UnboundLocalError, вызванный рекурсивным вызовом функции в Python?

Question

Я попытался преобразовать псевдокод для проблемы Максимального Subarray, приведенный во Введении в Алгоритмы. CLRS в полноценный рабочий код в Python.

Код:

def cross(A,low,mid,high): 
    left_sum = -float("inf") 
    s = 0 
    i = mid 

    while (i >= low): 
     s = s + A[i] 
     if s > left_sum: 
      left_sum = s 
      max_left = i 
     i = i - 1 

    right_sum = -float("inf") 
    s = 0 
    j = mid + 1 

    while (j < high): 
     s = s + A[j] 
     if s > right_sum: 
      right_sum = s 
      max_right = j 
     j = j + 1 

    return (max_left,max_right,left_sum+right_sum) 

def maxSubarray(A,low,high): 
    if high == low: return (low,high,A[low]) 
    else: 
     mid = (low+high)/2 
     (left_low,left_high,left_sum) = maxSubarray(A,low,mid) 
     (right_low,right_high,right_sum) = maxSubarray(A,mid+1,high) 
     (cross_low,cross_high,cross_sum) = cross(A,low,mid,high) 

     if (left_sum >= right_sum & left_sum >= cross_sum):return (left_low,left_high,left_sum) 
     elif (right_sum >= left_sum & right_sum >= cross_sum):return (right_low,right_high,right_sum) 
     else: return (cross_low,cross_high,cross_sum) 
t = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7] 

print maxSubarray(t,0,16) 

Когда я пытаюсь запустить, я получаю эту ошибку.

Ошибка:

Traceback (most recent call last): 
    File "/home/suyash/Downloads/python/max_subarray.py", line 64, in <module> 
    print maxSubarray(t,0,16) 
    File "/home/suyash/Downloads/python/max_subarray.py", line 49, in maxSubarray 
    (left_low,left_high,left_sum) = maxSubarray(A,low,mid) 
    File "/home/suyash/Downloads/python/max_subarray.py", line 49, in maxSubarray 
    (left_low,left_high,left_sum) = maxSubarray(A,low,mid) 
    File "/home/suyash/Downloads/python/max_subarray.py", line 49, in maxSubarray 
    (left_low,left_high,left_sum) = maxSubarray(A,low,mid) 
    File "/home/suyash/Downloads/python/max_subarray.py", line 49, in maxSubarray 
    (left_low,left_high,left_sum) = maxSubarray(A,low,mid) 
    File "/home/suyash/Downloads/python/max_subarray.py", line 53, in maxSubarray 
    (cross_low,cross_high,cross_sum) = cross(A,low,mid,high) 
    File "/home/suyash/Downloads/python/max_subarray.py", line 39, in cross 
    return (max_left,max_right,left_sum+right_sum) 
UnboundLocalError: local variable 'max_right' referenced before assignment 

Как я могу это исправить? Где я ошибся?

Answer 1

Два очень маленькие ошибки:

1. Ваш список т.е. t имеет длину 16. Это означает, что последний показатель равен 15. Таким образом, называют maxSubarray(t,0,15) не maxSubarray(t,0,16)
2. while (j <= high). Петля до j<= high не до j<high

Кроме этих двух исправлений, вы не должны установить любые значения по умолчанию для max_right или max_right. while любые условные обозначения if всегда будут иметь значение True во всех рекурсивных вызовах.

Демо:

>>> def cross(A,low,mid,high): 
...  left_sum = -float("inf") 
...  s = 0 
...  i = mid 
...  while (i >= low): 
...   s = s + A[i] 
...   if s > left_sum: 
...    left_sum = s 
...    max_left = i 
...   i = i - 1 
...  right_sum = -float("inf") 
...  s = 0 
...  j = mid + 1 
...  while (j <= high): # Loop until j<= high not until j<high 
...   s = s + A[j] 
...   if s > right_sum: 
...    right_sum = s 
...    max_right = j 
...   j = j + 1 
...  return (max_left,max_right,left_sum+right_sum) 
... 
>>> def maxSubarray(A,low,high): 
...  if high == low: return (low,high,A[low]) 
...  else: 
...   mid = (low+high)/2 
...   (left_low,left_high,left_sum) = maxSubarray(A,low,mid) 
...   (right_low,right_high,right_sum) = maxSubarray(A,mid+1,high) 
...   (cross_low,cross_high,cross_sum) = cross(A,low,mid,high) 
...   if (left_sum >= right_sum & left_sum >= cross_sum):return (left_low,left_high,left_sum) 
...   elif (right_sum >= left_sum & right_sum >= cross_sum):return (right_low,right_high,right_sum) 
...   else: return (cross_low,cross_high,cross_sum) 
... 
>>> t = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7] 
>>> print maxSubarray(t,0,15) # Last index = 15 not 16 
(7, 10, 43) # This shows max subarray is from index 7 to 10 i.e., [18,20,-7,12] and the sum is 43 

Answer 2

Вы забыли учитывать граничные условия.

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

Answer 3

Вы только когда-либо назначить max_right в if заявлении внутри while цикла, а это означает, что если вы получите исключение, то либо s > right_sum или j < high был никогда верно:

while (j < high): 
    s = s + A[j] 
    if s > right_sum: 
     right_sum = s 
     max_right = j 
    j = j + 1 

Вы должны дать max_right по умолчанию значение снаружи что while петля; max_right = high было бы уместно.