我尝试将 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
我怎样才能解决这个问题?我哪里出错了?