获取最大子数组的开头时出现问题

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标签下看到了一个类似的问题，但答案并不正确。为了方便起见，我提供了一个强力方法，我知道它是有效的，以及我一直在使用的迷你测试仪：

^{2}$

Answer 1

恕我直言，这很管用，而且是Python式的。在

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_），有sum、起始索引和结束索引。在

编辑：注意这里的结束索引是排他的。在

另外，如果有多个最优子阵列，则返回第一个和最长的子阵列。在