4

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

我尝试解决最大子数组问题，我在 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

4

2 回答 2

7

您提供的算法正在以更复杂的方式做同样的事情。为了正确解释它，我将在执行的各个步骤中将您提供的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 保持不变。对 2的ans 更改。

第二步：-

sum 更改为-2 并min 更改为-2。ans 仍然是2。这里要注意一件有趣的事情，根据 Wikipedia 对 Kadanes 算法的实现，在第二阶段，值current_sum将变为0，这是正确的继续方式。

但是在 codewars 实现中， 的值sum 仍然是-2。但是，如果您再仔细观察一下，您会发现sum-min在 codewars 实现中 的值为 0。这是一个非常重要的注意点。当 sum 的值小于 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)

第三步：-

对1.的sum 更改min 仍然保持不变。ans更改为3，这是正确的。这是怎么发生的？

在 Kadanes 算法中，您current_sum在此阶段将 的值更改为 3。在 codewars 实现中，sum他们所做的不是更改为 3，而是使用了一个min 变量，我再次重复该变量存储应该从 answer 中减去的数字，以便我们获得与 current_sum 中相同的值。从这部分算法中可以更清楚地看到这一点。

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

在这里，当我们min从您的sum. 它抵消了你答案中额外的负面影响。在这个数组 A 中，额外的负数是2 + (-4) = -2。在以下每个步骤中，我们将观察到这里的sum不包含最大连续子数组和。最大连续子数组和存储在 sum - min 中。这是该算法的关键。sum-min 是这里的 current_sum。以下是以下步骤：

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这里类似于current_sumKadanes 算法。

我还应该提到，如果输入数组由所有负数组成，您提供的 Kadanes 算法和 codewars 算法将不起作用。两者都不是为了它。如果您希望 Kadanes 算法适用于由所有负数组成的数组（将 current_sum 初始化为），则它在实现上存在小的差异。A[0]

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

于 2021-02-28T12:19:58.650 回答
1

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

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

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

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

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

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

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

于 2021-02-28T12:42:04.143 回答