java - Kadane 算法的 O(N) 中的最小总和子数组

Question

我们都知道最大和子数组和著名的Kadane's algorithm。 .但是我们也可以使用相同的算法来找到最小和吗？

我的看法是:

change the sign and find the max sum in that, same as the way we calculate the maximum sum subarray. Than change the sign of the elements in the array to make it in initial state.

如果有任何问题，请帮助我纠正算法。

极端情况:我知道如果所有元素都是正数就会出现问题，我们可以通过做一些预处理来处理这种情况，即如果所有元素都为 +ve 则遍历数组，而不是只返回最小数从阵列。

上述算法将有效并得到 dasblinkenlight 的良好支持(解释) .

Answer 1

Will the approach that I have mentioned work to find the minimum sum?

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

I know there is an issue if all the elements are positive

不，没有问题:当所有元素都为负时，请考虑原始的 Kadane 算法。在这种情况下，算法返回一个空序列，其总和为零 - 在这种情况下可能的最高值。换句话说，当所有元素都为负数时，最好的解决方案是不取任何元素。

您修改后的算法将在所有数字均为正数的情况下执行相同的操作:同样，您最好的解决方案是根本不接受数字。

如果您添加从算法返回的范围不能为空的要求，您可以稍微修改算法以找到最小的正数(或最大的负数)，以防 Kadane 的算法返回空范围作为最优解。