最大和连续子序列为零？

Question

我试图了解这个问题的解决方案："Given a sequence of numbers, find the maximum sum of a contiguous subsequence of those numbers."我在下面引用了一个解决方案和解释。

我不明白的是，在行 "maxendinghere = max(maxendinghere + s, 0)" 中，为什么 maxendinghere 永远为零？

def max_sum_subsequence(seq):
    maxsofar = 0
    maxendinghere = 0
    for s in seq:
        # invariant: maxendinghere and maxsofar are accurate
        # are accurate up to s
        maxendinghere = max(maxendinghere + s, 0)
        maxsofar = max(maxsofar, maxendinghere)
    return maxsofar

网站的解释是"Well, essentially maxendinghere is what’s accumulating the subsequences — it keeps rolling the next element into itself. Should this accumulated sum ever become negative we know that the subsequence-which-ends-here we’re currently tracking is worse than the empty subsequence-which-restarts-here; so we can reset our subsequence accumulator, and the first clause of the loop invariant still holds."

我不明白的是，假设我的序列是 2 -3 4：为什么 maxendinghere 永远为零？没有和为零的子序列。

（引自：http://wordaligned.org/articles/the-maximum-subsequence-problem）

Answer 1

在您的示例 2 -3 4 中，问问自己，以索引 1 结尾的最大总和是多少？ 2 - 3 是 -1。 -3 本身就是 -3。所以我们的最大总和是空总和，它选择 no 个元素，因此总和为 0.

记住，空子序列总是有可能的，sum 操作的标识值为 0。因此，例如，-2 -4 -3 中连续子序列的最大和就是 0 ，空子序列的总和。

验证这一点：

>>> max_sum_subsequence([-2, -4, -3])
0
>>> sum([]) == 0
True

要更改算法以使子序列的长度至少为 1，您可以通过更改两行代码来实现。

首先，将 maxsofar 的初始化更改为第一个元素或 None 如果它不存在。您可以使用您选择的任何默认值，而不是 None。默认值是为空输入序列返回的值。

maxsofar = seq and seq[0] or None

其次，将赋值更改为 maxendinghere 以强制它包含序列中至少一个元素的值：

maxendinghere = max(maxendinghere + s, s)

最大和连续子序列为零？

Maximum sum contiguous subsequence is zero?

python

algorithm

dynamic-programming

sequence