我知道最大子阵和问题及其O（n）算法。此问题通过使用循环链接列表来修改该问题：
求一个带最大和的循环链表中的数字序列。
如果所有条目的和为零呢？
对我来说，唯一的方法是修改数组解，让算法循环并在第一次迭代完成后从列表的开头重新开始。然后对整个列表执行相同的操作最多2次，并找到最大值。如果我这样做，则可能会有很多非常棘手的问题要处理，例如，如果列表看起来像：
2-2-2-2从后向前
那么不包含同一个元素两次是非常棘手的
有更好的算法吗？
谢谢！啊！
最佳答案
首先，不管数据结构是链表还是数组，为了简单起见，我将使用数组。
我不太明白你的算法，但你似乎要在原来的数组后面复制数组，然后在这个双数组上运行Kadane的算法这是一种错误的做法，@ranaldlam给出了一个反例。
要解决这个问题，我们需要从三个方面来讨论：
都是否定的在这种情况下，数组的最大值是答案，而O(N)扫描将完成这项工作；
最大子阵列不需要包装，例如a = {-1, 1, 2, -3}。在这种情况下，一个普通的KADAN算法将完成这项工作，时间复杂度O(N)；
最大子阵列需要一个包装，例如a = {1, -10, 1}。实际上，这种情况意味着另一个事实：因为最大子阵列内部的元素需要封装，所以不在最大子阵列内的元素不需要封装。因此，只要我们知道这些非贡献元素的和，我们就可以通过从数组的总和中减去max_non_贡献元素的和来计算贡献元素的正确和。
但是在案例3中如何计算max_non_contributing_sum？这有点棘手：因为这些不起作用的元素不需要包装，所以我们可以简单地反转每个元素的符号，并在这个需要O(N)的反转数组上运行kadane的算法。
最后，我们应该比较非包装（案例2）和包装（案例3）的总和，答案应该是更大的一个。
总之，所有的情况都需要O(N)，因此算法的复杂度为O(N)。
关于java - 如何在循环链表中找到最大子序列和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25646482/