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

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

只需将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 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;

}