我试图按照Cormen算法的方法来解决使用Python.For动态规划最大总和子阵列这个问题我已经创建了这是工作的罚款最大交叉子阵列码。
def maxcrosssub(arr, low, mid, high):
left_sum = float("-inf")
sum = 0
for i in range(mid, low-1, -1):
sum += arr[i]
if sum > left_sum:
left_sum = sum
max_left = i
right_sum = float("-inf")
sum = 0
for j in range(mid+1, high):
sum += arr[j]
if sum > right_sum:
right_sum = sum
max_right = j
return(max_left, max_right, left_sum+right_sum)
但问题是,在主程序。
def max_subarray(arr, low, high):
if low == high:
return (low, high, arr[low])
mid = (low+high)//2
left_low, left_high, left_sum = max_subarray(arr, low, mid)
right_low, right_high, right_sum = max_subarray(arr, mid+1, high)
cross_low, cross_high, cross_sum = maxcrosssub(arr, low, mid, high)
if left_sum >= right_sum and left_sum >= cross_sum:
return(left_low, left_high, left_sum)
elif right_sum >= left_sum and right_sum >= cross_sum:
return(right_low, right_high, right_sum)
else:
return(cross_low, cross_high, cross_sum)
我得到这个错误
UnboundLocalError: local variable 'max_right' referenced before assignment.
我一直在使用全局变量名以下的堆栈溢出一些答案尝试,但它仍然没有工作。任何人都可以建议我做错了什么?
问题是从第一功能maxcrosssub
的到来,恰恰从一个事实,即在某些情况下max_right
被使用(参考)被初始化之前(分配)。例如,如果条件sum > left_sum
是永远不会满足。
分配一个值开始到max_right
(之前它的引用)
我试图按照Cormen算法的方法来解决使用Python.For动态规划最大总和子阵列这个问题我已经创建了这是工作的罚款最大交叉子阵列码。
def maxcrosssub(arr, low, mid, high):
left_sum = float("-inf")
sum = 0
# Here is where you can assign a value to 'max_right'
max_right = 0 # For example
for i in range(mid, low-1, -1):
sum += arr[i]
if sum > left_sum:
left_sum = sum
max_left = i
right_sum = float("-inf")
sum = 0
for j in range(mid+1, high):
sum += arr[j]
if sum > right_sum:
right_sum = sum
max_right = j
return(max_left, max_right, left_sum+right_sum)