O(N)中最小和子阵的Kadane算法

Question

我的看法是：

改变符号并在其中找到最大和，与我们计算最大和子数组的方法相同。改变数组中元素的符号使其处于初始状态。

如果algo有任何问题，请帮助我更正。

拐角情况：我知道如果所有元素都是正的就会有问题，我们可以通过做一些预处理来处理这种情况，即如果所有元素都是+Ve，就遍历数组，而不仅仅是从数组返回最小值。

上面提到的算法将工作，并得到DasBlinkenlight的良好支持（解释）。

Answer 1

我提到的方法能找到最小和吗？

是的，会的。您可以将求最小和的问题重新表述为求绝对值最大的负和。当你切换你的数字的符号，并保持算法的其余部分就位时，这就是算法要返回给你的数字。

我知道如果所有的因素都是积极的就有问题了

不，没有问题：当所有元素都是负数时，考虑最初的Kadane算法。在这种情况下，算法返回一个零和的空序列--在这种情况下可能的最高的一个。换句话说，当所有元素都是负数时，你最好的解决办法就是什么都不拿。

当所有的数字都为正时，修改后的算法也会这样做：同样，最好的解决方案是完全不取数。

如果您添加了一个要求，即从算法返回的范围不能为空，那么您可以稍微修改该算法，以找到最小正数（或最大负数），以防Kadane的算法返回一个空范围作为最优解。