How to fix an UnboundLocalError caused due to a recursive function call in Python?

Question

I tried to convert the pseudo-code for the Maximum-Subarray problem given in Introduction to Algorithms By CLRS into a full-fledged working code in Python.

Code:

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)

When I try to run, I get this error.

Error:

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

How can I fix this? Where have I gone wrong?

Answer 1

Two really small mistakes:

1. Your list i.e., t is of length 16. This means last index is 15. Thus call maxSubarray(t,0,15) not maxSubarray(t,0,16)
2. while (j <= high). Loop until j<= high not until j<high

Also with these two fixes, you don't need to set any default values to max_right or max_right. The while any if conditionals will always be True in every recursive call.

Demo:

>>> 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

You forgot to account for boundary conditions.

There may come a point when a conditional that normally succeeds suddenly fails, leaving a variable unbound. You need to make sure that the variable has a sane default regardless.

Answer 3

You only ever assign max_right in an if statement inside a while loop, meaning that if you get the exception, then either s > right_sum or j < high was never true:

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

You should give max_right a default value outside that while loop; max_right = high would be appropriate here.