如何查找循环链表中的最大子序列总数

Question

我知道最大子数组总和问题及其O（n）算法。此问题通过使用循环链表来修改该问题：

查找具有最大总和的循环链表中的数字序列。
现在如果所有条目的总和为零，该怎么办？

对我来说，唯一的方法是修改阵列解决方案，让算法循环，并在第一次迭代完成后从列表开始处重新开始。然后做同样的事情达到整个列表的2倍，并找到最大值。不利的一面是，可能有很多非常棘手的处理，如果我做这种方式，例如，如果列表看起来像：

2 - 2 - 2 - 2回前

然后，它是非常棘手不包括相同的元素两次

有没有更好的算法？

谢谢！

Answer 1

你绝对正确。没有更好的算法。

Answer 2

首先，数据结构是链表还是数组并不重要，所以为了简单起见，我将使用数组。

我并不十分理解你的算法，但似乎你要做的事情就像在原始数据的后面重复数组，然后在这个doubled-array上运行Kadane的算法。这是一个错误的方法，@RanaldLam给出了一个反例。

为了解决这个问题，我们需要讨论的三种情况：

1. 均为阴性。在这种情况下，数组的最大值就是答案，并且O(N)扫描将完成这项工作;
2. 最大子数组不需要换行，例如a = {-1, 1, 2, -3}。在这种情况下，正常的Kadane算法可以完成这项工作，时间复杂度为O(N);
3. 最大的子阵列需要打包，例如a = {1, -10, 1}。实际上，这种情况意味着另一个事实：由于最大子数组内的元素需要打包，因此不在最大子数组内的元素不需要打包。因此，只要我们知道这些非贡献元素的总和，就可以通过从数组总和中减去max_non_contribute_sum来计算贡献元素的正确总和。

但是如何计算案例3中的max_non_contributing_sum？这有点棘手：因为这些不贡献的元素不需要包装，所以我们可以简单地反转每个元素的符号，并在该反转阵列上运行Kadane的算法，这需要O(N)。

最后，我们应该比较非包装（情况2）和包装（情况3）的总和，答案应该是较大的一个。

总结，所有案例都需要O(N)，因此该算法的总体复杂度为O(N)。