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

您是否曾经感觉自己的大脑不适合算法？

我尝试解决最大子数组问题 https://en.wikipedia.org/wiki/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 https://codepen.io/florianmartens/pen/zYoWwVX?editors=1010一些例子

您提供的算法正在做同样的事情，但方式更复杂。为了正确解释它，我将比较代码战争算法您提供的卡丹算法在其执行的各个步骤中。

让我们考虑一下数组：

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

这里是代码战争算法您提供：

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

这是执行卡丹算法维基百科中提到：

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 and min 保持不变. The ans 更改为 2.

第二步：-

sum 更改为 -2 and min 更改为-2。这ans is still2. 这里需要注意一个有趣的事情，根据维基百科对 Kadanes 算法的实现，在第二阶段的值current_sum will change到 0 这是正确的处理方法。

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

以下是迄今为止变量值的记录：

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

第三步：-

The sum 更改为 1. min 仍然保持不变。的答案更改为3 哪个是正确的。这是怎么发生的呢？

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

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

这里当我们减去min从你的sum. 它抵消了你答案中额外的否定。在这个数组 A 中，额外的负数是2 + (-4) = -2。在以下每个步骤中，我们将在这里观察到sum is not包含最大连续子数组和。最大连续子数组总和存储在 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_sumKadane 算法。

我还应该提到，您提供的 Kadanes 算法和 codewars 算法将not工作，如果输入数组由所有负数组成。两者都不是为此目的。如果您希望 Kadanes 算法适用于由所有负数组成的数组（将 current_sum 初始化为A[0]).

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