java - 如何在循环链表中找到最大子序列和

Question

我知道最大子数组和问题及其 O(n) 算法。这个问题通过使用循环链表修改了那个问题:

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

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

2 - 2 - 2 - 2 从后到前

那么不包含同一个元素两次就非常棘手了

有没有更好的算法？

谢谢!!

Answer 1

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

我不太明白你的算法，但你似乎打算做一些事情，比如在原数组的后面复制数组，然后在这个双数组上运行 Kadane 的算法 .这是一种错误的方法，@RanaldLam 给出了一个反例。

要解决这个问题，我们需要分三种情况来讨论:

1. 全部为阴性。在这种情况下，数组的最大值就是答案，O(N) 扫描即可完成工作；
2. 最大子数组不需要换行，例如a = {-1, 1, 2, -3}。在这种情况下，一个普通的 Kadane 算法就可以完成这项工作，时间复杂度 O(N);
3. 最大子数组需要换行，例如a = {1, -10, 1}。实际上，这种情况暗示了另一个事实:既然最大子数组内的元素需要换行，那么不在最大子数组内的元素就不需要换行。因此，只要我们知道这些非贡献元素的总和，我们就可以通过从数组总和中减去 max_non_contributing_sum 来计算正确的贡献元素总和。

但是如何计算情况 3 中的 max_non_contributing_sum？这有点棘手:因为这些无贡献的元素不需要换行，所以我们可以简单地反转每个元素的符号并在这个反转数组上运行 Kadane 算法，这需要 O( N).

最后，我们应该比较非包装(案例 2)和包装(案例 3)的总和，答案应该更大。

总而言之，所有情况都需要O(N)，因此算法的总复杂度为O(N)。