从cormens算法最大子阵列的问题没有限制本地错误

问题描述 投票:1回答:1

我试图按照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.

我一直在使用全局变量名以下的堆栈溢出一些答案尝试,但它仍然没有工作。任何人都可以建议我做错了什么?

python algorithm sum max dynamic-programming
1个回答
1
投票

The problem

问题是从第一功能maxcrosssub的到来,恰恰从一个事实,即在某些情况下max_right被使用(参考)被初始化之前(分配)。例如,如果条件sum > left_sum是永远不会满足。

Solution

分配一个值开始到max_right(之前它的引用)

Try this

我试图按照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)
© www.soinside.com 2019 - 2024. All rights reserved.