我试图将 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
我该如何解决这个问题?我哪里出错了?
最佳答案
两个非常小的错误:
- 您的列表即
t
长度为 16。这意味着最后一个索引是 15。因此调用maxSubarray(t,0,15)
不是maxSubarray(t,0,16)
-
while (j <= high)
.循环直到j<= high
直到j<high
此外,通过这两个修复,您无需将任何默认值设置为 max_right
或 max_right
. while
任何if
在每次递归调用中,条件总是为真。
演示:
>>> 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
关于python - 如何修复由于 Python 中的递归函数调用导致的 UnboundLocalError?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27480355/