python - Kadane的算法，连续元素的最大求和

Question

如何跟踪最大连续和问题的起始索引？

index_pairs[] 是 max cont 的起始索引 [0] 和结束索引 [1]。总和。

我总能找到最大连续的最后一个索引求和，但我的起始索引 index_pairs[0] 将返回如果最大和之后有更大的数字，则索引不正确。

我的思路:为了知道起始索引的和，必须知道当 maxendinghere 从零开始与我的 iterable 列表的整数相加时。然而，当maxendinghere如果小于则永远为零到零，即使下一个连续的也更新总和(可能不是最大的总和)正在求和。

---

有没有办法找到我的最大连续求和索引的起始索引

from random import randrange
iterable = [randrange(-10,10) for r in xrange(100)]

def max_continuous_sequence(iterable):
    maxsum, maxendinghere = 0, 0
    index_pairs = [0,0]
    for i,x in enumerate(iterable):
        # summing next numbers
        maxendinghere += x
        if maxsum < maxendinghere:
            # found a higher sum
            maxsum = maxendinghere
            index_pairs[1] = i
        elif maxendinghere < 0:
            # resets the max here if next element is less than zero
            maxendinghere = 0
            # starts off the index at where we ended last
            index_pairs[0] = i+1
    return (index_pairs[0],index_pairs[1])

Answer 1

您可以颠倒元素的顺序，运行您的算法来计算最后一个索引(实际上是初始序列的第一个索引)，然后计算它与序列末尾的距离以获得答案.加法是可交换的:)