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_contribution_sum来计算贡献元素的正确和

但是在案例3中如何计算max_non_contributing_sum？这有点棘手：因为这些非贡献元素不需要包装，所以我们可以简单地反转每个元素的符号，并在这个反转数组上运行Kadane的算法，它需要^{

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

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

Answer 2

你完全正确。没有比这更好的算法了