我试图将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
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句