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

Question

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

我的看法是：

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

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

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

上述算法将有效并得到dasblinkenlight的良好支持（解释）。

Answer 1

我提到的方法能否找到最小金额？

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

我知道如果所有元素都是正的就会有问题

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

如果所有数字都是正数，您修改后的算法将执行相同的操作：同样，您最好的解决方案是根本不接受数字。

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

Answer 2

static void subArraySumMin(int a[]) {
        int minendingHere = 0;
        int minSoFar = a[0];

        for (int i = 1; i < a.length; i++) {
            minendingHere = Math.min(a[i], minendingHere + a[i]);
            minSoFar = Math.min(minSoFar, minendingHere);
        }

        System.out.println(minSoFar);
    }

Answer 3

只需将最大值替换为最小值

//O(n)
public static int minSubArraySum(int[] arr) {
    int minSum = 0;
    int curSum = 0;
    for (int num : arr) {
        curSum += num;
        minSum = Math.min(minSum, curSum);
        curSum = Math.min(curSum, 0);
    }
    return minSum;
}

Answer 4

function minSubArray(arr) {
let min = 0;
let currSum = 0;
for (let i = 0; i < arr.length; i++) {
    currSum = currSum + arr[i];
    if (currSum > 0) {
        currSum = 0;
    }
    if (currSum < min) min = currSum;
}
return min;

}