最大子数组问题 - 最小值解？

Question

你有没有觉得你的脑袋不适合算法？

我尝试解决 maximum subarray problem 我在 Codewars 上遇到了这个解决方案：

var maxSequence = function(arr){
  var min = 0, ans = 0, i, sum = 0;
  for (i = 0; i < arr.length; ++i) {
    sum += arr[i];
    min = Math.min(sum, min);
    ans = Math.max(ans, sum - min);
  }
  return ans;
}

console.log(maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, -4]));

我了解如何使用 Kadane's algorithm:

以线性时间复杂度解决此问题

var maxSequence = function(arr){
  let max = 0;
  let localMax = 0;

  for (let i = 0; i < arr.length; i++) {
    localMax = Math.max(localMax + arr[i], arr[i]);
    max = Math.max(localMax, max);
  }

  return max;
}

console.log(maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, -4]));

但我不明白为什么第一个解决方案有效。我根本无法理解它背后的想法。我觉得需要一点帮助来克服困难。

编辑：这里是 Codepen 和一些例子

Answer 1

您提供的算法以更复杂的方式做同样的事情。 为了正确解释，我将比较您提供的 Codewars 算法 和 Kadanes 算法 在执行的各个步骤.

让我们考虑数组：

[2 -4 3 2 6 -10 -12 20]

这是您提供的 Codewars 算法：

var maxSequence = function(arr){
    var min = 0, ans = 0, i, sum = 0;
    for (i = 0; i < arr.length; ++i) {
        sum += arr[i];
        min = Math.min(sum, min);
        ans = Math.max(ans, sum - min);
    }
    return ans;
}

这里是维基百科中提到的Kadanes算法的实现：

def max_subarray(numbers):
"""Find the largest sum of any contiguous subarray."""
best_sum = 0  # or: float('-inf')
current_sum = 0
for x in numbers:
    current_sum = max(0, current_sum + x)
    best_sum = max(best_sum, current_sum)
return best_sum

第一步：-

sum 更改为 2，min 保持不变。 ans 变为 2.

第二步：-

sum更改为-2，min更改为-2。 ans 仍然是 2. 这里要注意一个有趣的事情，根据维基百科的 Kadanes 算法的实现，在第二阶段 current_sum 的值将将更改为 0，这是继续的正确方法。

但是在codewars实现中，sum的值仍然是-2。但是，如果您更仔细地注意，您会发现 sum-min 的值在 codewars 实现中为 0。这是一个非常重要的注意点。而不是当它的值小于 0 时将 sum 更改为 0。我们 存储必须从 sum 中减去以使净和为 0 的最小数。 这个值是存储在 min 中，这也解释了为什么这样命名。

这里是目前变量值的记录：

 sum    min    ans
  2      0      2     //ans = max(0, 2-0)
 -2     -2      2     //ans = max(2, -2+2)

第三步：-

sum 改为 1. min 还是一样。 ans 更改为 3 这是正确的。这是怎么发生的？

在 Kadanes 算法中，您在此阶段将 current_sum 的值更改为 3。在 codewars 实现中，他们没有将 sum 更改为 3，而是使用了一个 min 变量，我再次重复该变量存储应该从答案中减去的数字，以便我们获得相同的值正如我们在 current_sum. 中所做的那样，从算法的这一部分就更清楚了。

ans = Math.max(ans, sum - min);   //sum-min is current_max

这里当我们从你的sum中减去min。 它抵消了你答案中额外的否定。 在这个数组 A 中，额外的否定是 2 + (-4) = -2。在接下来的每一步中，我们都会观察到这里的sum是not包含最大的连续子数组和。 sum - min 中存储的是最大的连续子数组和。 这是这个算法的关键。 这里的current_sumsum-min是。以下是以下步骤：

sum    min    ans
 1     -2      3      //ans = max(2, 1+2)
 3     -2      5      //ans = max(3, 3+2)
 9     -2      11     //ans = max(5, 9+2)
-1     -2      11     //ans = max(11, -1+2)

有趣的是，即使在最后一步中 sum 的值为负数，min 的值也没有改变。这是为什么？答案是不需要。如果你看sum-min是这种情况，它是1并且不小于0。因此有可能如果A中当前索引后面有足够的正数，则sum的值 - min 可能会超过 ans. 的当前值如果你将运行 Kadanes 算法干到这一步，你会注意到即使在这个阶段 current_sum 的值也不会变为 0 , 它将是 1.

剩余步骤：-

sum    min    ans
-1     -2      11     //ans = max(11, -1+2)
-13    -13     11     //ans = max(11, -13+13)
 7     -13     20     //ans = max(11,  7+13)

这个实现中最重要的一点，sum-min这里类似于Kadanes算法的current_sum

我还应该提到，如果 输入数组包含所有负数 ，您提供的 Kadanes 算法和 codewars 算法将无效 .两者都不是为了它。如果您希望 Kadanes 算法适用于由所有负数组成的数组（将 current_sum 初始化为 A[0]）。

如果您在理解我的解释时遇到任何问题，请发表评论。

Answer 2

我不认为 Codewars 算法适用于每个测试用例。

以下是该算法会失败的测试用例：

测试用例1： arr = [-1]

测试用例2： arr = [-1, -2]

对于这两个测试用例，被测算法给出的输出等于 0，这不是正确答案。

PS: 我检查了Codewars问题。该问题的测试用例还不全面，这个问题有问题。

所以就目前而言，Kadane的算法是解决线性时间复杂度问题的一个不错的选择。

最大子数组问题 - 最小值解？

Maximum subarray problem - min value solution?

javascript

algorithm

kadanes-algorithm