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

Question

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

我的看法是：

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

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

极端情况：我知道如果所有元素都是正数，则存在问题，我们可以通过进行一些预处理来处理这种情况，即如果所有元素都是 +ve 则遍历数组，而不仅仅是从数组中返回最小数。

dasblinkenlight可以很好地支持（解释）上述算法。

Answer 1

我提到的方法是否可以找到最小金额？

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

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

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

如果所有数字都是正数，您修改后的算法也会这样做：同样，您最好的解决方案是根本不取数字。

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

Answer 2

只需将 max 替换为 min 即可。

//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 3

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);
    }