Kadane算法在O（N）中的最小和子arrays
我们都知道最大和子arrays和着名的Kadane算法 。 但是我们可以使用相同的算法来找到最小总和吗？
我的看法是：
改变符号并找到最大总和，与我们计算最大总和子arrays的方式相同。 然后更改数组中元素的符号以使其处于初始状态。
如果有任何问题，请帮我纠正算法。
极端情况：我知道如果所有元素都是正数会有问题我们可以通过做一些预处理来处理这种情况，即如果所有元素都是+ ve而不是从数组中返回最小数字则遍历数组。
上面提到的算法将由dasblinkenlight工作并得到很好的支持（解释）。
我提到的方法是否可以找到最小数额？
是的，它会。 您可以重新说明找到最小总和的问题，即找到具有最大绝对值的负和。 当您切换数字的符号并保留算法的其余部分时，这就是算法将返回给您的数字。
我知道如果所有要素都是积极的，那么就会出现问题
不，没有问题：当所有元素都是负数时，考虑原始的Kadane算法。 在这种情况下，算法返回一个零序的空序列 – 在这种情况下可能的最高值。 换句话说，当所有元素都是负数时，最好的解决方案就是不采用任何元素。
如果所有数字都是正数，那么您修改后的算法将会执行相同的操作：同样，您最好的解决方案是根本不接受数字。
如果添加一个要求，即从算法返回的范围可能不为空，则可以稍微修改算法以找到最小的正数（或最大的负数），以防Kadane的算法返回空范围作为最佳解决方案。
只需用min替换max。
//O(n) public static int minSubArraySum(int[] arr) { int minSum = 0; int curSum = 0; for (int i : arr) { curSum += i; minSum = Math.min(minSum, curSum); curSum = Math.min(curSum, 0); } return minSum; }