我正在学习《算法入门》一书,并使用给出的算法制作程序,但程序并没有按预期工作。
可能上一个函数的和加在了新的和上,所以我不知道怎么打印出来。
当我放置一个元素列表时,输出和预期的一样,但是当我放置两个或更多元素列表时,比如说[2,3]时,我得到了不期望的输出4

def max_crossing_subarray(array,low,mid,high):
    left_sum = -1000
    sum_ar = 0

    for i in range(mid, low-1, -1):
        sum_ar = sum_ar + array[i]
        if sum_ar>left_sum:
            left_sum = sum_ar
            max_left = i

    right_sum = -1000
    sum_ar = 0

    for i in range(mid,high):
        sum_ar = sum_ar + array[i]
        if sum_ar>right_sum:
            right_sum = sum_ar
            max_right = i

    return [max_left, max_right, left_sum + right_sum]

def max_subarray(array, low, high):
    if low==high:
        return [low, high, array[low]]
    else:
        mid = int((low + high)/2)
        left_low, left_high, left_sum = max_subarray(array, low, mid)
        right_low, right_high, right_sum = max_subarray(array,mid+1,high)
        cross_low, cross_high, cross_sum = max_crossing_subarray(array,
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]

arr = [2,3]
ar= max_subarray(arr, 0, len(arr)-1)
print(ar)

当我输入列表[2]时,我得到了输出[0,0,2][低,高,和]
但对于[2,3]和[2,5],我得到的输出分别为[0,0,4]和[1,1,5],这不是预期的。

最佳答案

在计算最大交叉子数组时,for语句范围的秒数应该从mid+1开始,到high+1结束。首先将中间元素right now添加到左和右和,然后在最后一个元素之前完成元素的求和。

10-08 04:06
查看更多