最大子阵列问题-最小值解决方案？

您提供的算法正在以更复杂的方式做同样的事情。为了正确地解释它，我将比较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-mincodewars 实现中的值为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)    

第三步：-

sum 对1.的更改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]），则它在实现上存在小的差异。

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