python - 问题获取最大子数组的开始

Question

我正在尝试实现一种方法来获取 maxSubArray 总和以及关联的开始和结束索引。作为引用，maxSubArray 是连续的子数组，其整数和在所有子数组中最大。我的总和是正确的，结束索引是正确的，但我在开始时遇到了麻烦。我已经解释了一个微不足道的案例，但无论我做什么，我似乎都无法解释所有的案例。每当我解释一个，另一个就会出现。显然在线性时间内获得总和是可能的，但我似乎无法找到一种有效地获得正确起始索引的方法。

def maxSubArray(seq):
    #max_i = max ending at i, max_gen = best max up until i
    max_i = max_gen = beg = end = prev_max = 0

    for i in xrange(len(seq)):
        #use dynamic programming to get maxSubArray sum (works)
        max_i = max(0, max_i + seq[i])
        max_gen = max(max_gen, max_i)

        #get correct end (works)
        if prev_max < max_gen:
            end = i

        prev_max = max_gen

    if max_gen == 0:
        max_gen = max(seq)
        beg = end = seq.index(max_gen)

    return [max_gen, beg, end]

就像我说的，我尝试了很多东西，但随着每一种新方法都会引入新/旧问题，我会继续删除它们。有人有任何建议/解决方案吗？我在Java标签下看到了类似的问题，但答案不正确。为方便起见，我提供了一种我知道有效的蛮力方法，以及我一直在使用的迷你测试器:

def bruteForceCheck(seq):
    maxV = [float('-inf'), 0, 0]

    for i in xrange(len(seq)):
        for j in xrange(i,len(seq)):
            if (sum(seq[i:j+1]) > maxV[0]):
                maxV = [sum(seq[i:j+1]), i, j]

    return maxV

if __name__ == "__main__":

    for i in xrange(1000):
        l = []
        for j in xrange(15):
            num = random.randint(-1000,1000)

            #didn't feel like dealing with issue of two methods 
            #choosing to count or not count 0s
            while (num == 0):
                num = random.randint(-1000,1000)

            l.append(num)

        msa = maxSubArray(l)
        bfc = bruteForceCheck(l)

        if msa != bfc:
            print l
            print msa
            print bfc
            break

Answer 1

请原谅，但这有效并且是 Pythonic。

def maxSubArray(seq):
    all_sum = cur_sum = 0
    all_beg = cur_beg = 0
    all_end = 0
    for cur_end, x in enumerate(seq, 1):
        if cur_sum + x > 0:
            cur_sum += x
            if all_sum < cur_sum:
                all_sum = cur_sum
                all_beg, all_end = cur_beg, cur_end
        else:
            cur_sum = 0
            cur_beg = cur_end
    return all_sum, all_beg, all_end

算法是一样的。对于此处结束 (cur_) 和总体 (all_) 的数组，存在总和、开始索引和结束索引。

编辑:请注意，此处的结束索引是独占的。

此外，如果有多个最优子数组，则返回第一个和最长的子数组。