连续子序列的最大和为零？

我试图理解这个问题的解决方案：“给定一个数字序列，找到这些数字的连续子序列的最大总和。”我在下面引用了一个解决方案和解释。连续子序列的最大和为零？

我不明白的是，在“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

从网站上的解释是“好了，基本上maxendinghere是什么积累的子序列 - 它不断滚动的下一个元素到自身如果这种积累和以往任何时候都变得消极，我们知道，子，其中，ends-在这里我们目前的跟踪比空的子序列更糟糕 - 它重新启动 - 这里;所以我们可以重置我们的子序列累加器，并且循环不变的第一个子句仍然成立。

我不明白的是，让我们说我的顺序是2 -3 4：为什么maxendinghere会是零？没有任何总和为零的子序列。

（行情从：http://wordaligned.org/articles/the-maximum-subsequence-problem）

来源

2015-04-04 randomUser47534

在你的榜样2 -3 4，问问自己，什么是索引1结束之和最大？ 2 - 3是-1。 -3本身是-3。因此，我们的最高金额，然后空的总和，它选择没有元素，因此具有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)

来源

2015-04-04 03:21:13 Shashank

连续子序列的最大和为零？

回答

相关问题