Kadane算法在O(N)时间复杂度内求最小和子数组

Question

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

我的想法是：

将所有元素取反，然后在其中找到最大子数组和，就像我们计算最大子数组和一样。然后再将数组中的元素取反以使其回到初始状态。

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

特殊情况：我知道如果所有元素都是正数，会出现问题，我们可以通过一些预处理来处理这种情况，即遍历数组，如果全是正数，则返回数组中的最小数字。

上述算法将有效，并由dasblinkenlight提供了良好的支持（解释）。

- Trying

---

如果全部元素都是正数，为什么它不能工作？在这种情况下，空序列的最小和为0，这将被正确地找到。 - Henry

@Henry - 他可能想要找到一个大小为_k_的子数组的最小和，其中 k ≤ _N_。 - DaoWen

在这种情况下，我们可以遍历数组，如果我们看到所有元素都是正数，那么我们可以取元素的最小值，这比返回0更合适。谢谢。但是主要问题在于，我提到的方法是否适用于找到最小和？ - Trying

Answer 1

我提到的方法能否用于找到最小总和？

是的，可以。您可以将查找最小总和的问题重新表述为查找具有最大绝对值的负总和。当您切换数字的符号并保持其余算法不变时，该算法将返回给您的数字即为所需数字。

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

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

当所有数字都是正数时，您修改后的算法也将执行相同操作：您的最佳解决方案仍然是不取任何数字。

如果您添加一个要求，即从算法返回的范围不能为空，则可以稍微修改算法，以便在Kadane算法将空范围作为最佳解决方案返回时查找最小的正数（或最大的负数）。

- Sergey Kalinichenko

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

- Hiccup

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

- yadongwen

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;

}

- Tapu

---

请修复您代码中的格式问题。此外，它不应该检查currSum是否大于0，而是应该检查是否小于0？不确定是否有错误，但在其他答案中，“min”可以低于0，而在您的答案中，它不能超过0（或者如果您修复了if，则不能低于0）。 - Moritz Ringler