最大和子数组 python

Question

我正在按照书本 'Introduction to Algorithm' 并使用给出的算法来制作程序，但程序没有按预期运行。

可能是前一个函数的总和加到新的总和上，因此它被打印出来我不知道如何。当我放置一个元素列表时，输出符合预期，但是当我放置 2 个或更多元素列表时，说 [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] #[low, high, sum] 但是对于 [2,3] 和 [2,5]，我得到的输出分别为 [0, 0, 4] 和 [1, 1, 5]，这与预期不同。

Answer 1

在计算最大交叉子数组时，第二个for语句范围应该从mid + 1开始到high + 1结束。首先中间元素现在被添加到左右总和，其次你在元素之前完成求和最后一个。

最大和子数组 python

Maximum sum sub array python

algorithm

max

divide-and-conquer

sub-array

python-3.x