Python中max子数组的不正确索引

Question

我用Python编写了Max子数组问题的蛮力实现和分而治之实现。测试是通过绘制整数的随机样本来运行的。

当输入数组的长度很大时，在__main__中的断言失败，因为递归算法没有返回正确的答案。但是，当数组小于10个元素时，这两种算法是一致的(这是近似的，每次执行失败输入的实际大小都不同)。这个问题似乎与偶数或奇数数组长度无关，但似乎与数组的索引方式有关。

对不起，如果我错过了一些愚蠢的东西，但是为什么当输入数组开始变大时，递归算法就停止返回正确的输出？

# Subarray solutions are represented by an array in the form
# [lower_bound, higher_bound, sum]

from sys import maxsize
import random
import time

# Brute force implementation (THETA(n^2))
def bf_max_subarray(A):
    biggest = -maxsize - 1

    left = 0
    right = 0

    for i in range(0, len(A)):
        sum = 0
        for j in range(i, len(A)):
            sum += A[j]
            if sum > biggest:
                biggest = sum
                left = i
                right = j   

    return [left, right, biggest]

# Part of divide-and-conquer solution   
def cross_subarray(A, l, m, r): 
    lsum   = -maxsize - 1
    rsum   = -maxsize - 1
    lbound = 0
    rbound = 0

    tempsum = 0
    for i in range(m, l-1, -1):
        tempsum += A[i]
        if tempsum > lsum:
            lsum = tempsum
            lbound = i

    tempsum = 0
    for j in range(m+1, r+1):
        tempsum += A[j]
        if tempsum > rsum:
            rsum = tempsum
            rbound = j

    return [lbound, rbound, lsum + rsum]

# Recursive solution
def rec_max_subarray(A, l, r):
    # Base case: array of one element
    if (l == r):
        return [l, r, A[l]]
    else:
        m = (l+r)//2

        left  = rec_max_subarray(A, l, m)
        right = rec_max_subarray(A, m+1, r)
        cross = cross_subarray(A, l, m, r)

        # Returns the array representing the subarray with the maximum sum.
        return max([left, right, cross], key=lambda i:i[2])

if __name__ == "__main__":
    for i in range(1, 101):
        A = random.sample(range(-i*2, i), i)

        start = time.clock()
        bf = bf_max_subarray(A)
        bf_time = time.clock() - start

        start = time.clock()
        dc = rec_max_subarray(A, 0, len(A)-1)
        dc_time = time.clock() - start

        assert dc == bf # Make sure the algorithms agree.

Answer 1

具有最大和的子数组由表单[left_bound, right_bound, sum]的数组表示。

但是，多亏了return max([left, right, cross], key=lambda i:i[2])，rec_max_subarray为A返回了正确的最高金额，但有可能返回与bf_max_subarray中返回的起诉书不匹配的起诉书。我的错误是假设具有最大和的子数组的边界是唯一的.

解决方案是要么修复选择子数组的条件，要么使用assert dc[2] == bf[2]断言和相等。