Kadane算法与最大子阵列问题

由 Mux 赞助的 DEV 全球展示挑战赛：展示你的项目！

一个常见的面试题是：给定一个整数数组，返回该数组中任意一个子数组的最大和。这里的“子数组”指的是连续的整数，可以只包含一个整数，也可以包含数组中的所有整数。在这个问题中，你可以假设数组包含负数——否则，最大和的子数组就等于整个数组。（你可以在这里找到 LeetCode 上的题目。）

例如，假设你得到一个输入数组[2, 1, -2, 3, 2]，其中包含子数组 [2]、[2, 1]、[2, 1, -2] 等等。仅从这个数组来看，你可能会认为子数组的最大和是 5，即最后两个元素之和。然而，最大子数组实际上是整个数组，其元素之和为 6。

解决这个问题的一种暴力解法是，对输入数组的每个子数组进行编译，计算其元素之和，然后返回最大值。这种方法的时间复杂度为 O(n^2)——通常这意味着存在更高效的方法。

在这篇博文中，我将详细介绍使用 Kadane 算法解决这个问题的方法，该方法可以在 O(n) 时间内完成。本文基于 CS Dojo 制作的一个视频（链接在此），我强烈建议大家观看该视频。

卡丹算法

这种方法需要检查每个元素的最大子数组是什么。卡丹算法指出，每个元素的最大子数组要么是当前元素本身，要么是当前元素加上以前一个元素结尾的最大子数组。

让我们看看在示例输入上会是什么样子。首先，我们可以将当前最大值初始化为第一个元素，因为没有先前的最大值可供比较。出于同样的原因，我们也把全局最大值初始化为第一个元素。因此，当前最大值是 2，全局最大值也是 2。

接下来，我们继续检查下一个元素，也就是 1。根据 Kadane 的理论，最大和要么是当前元素本身，要么是当前元素与前一个最大和之和。在本例中，我们将当前元素 1 与 1+2（当前元素与前一个最大和之和）进行比较。3 更大，因此当前最大值变为 3。现在，我们需要检查当前最大值是否大于前一个子数组中的最大和，如果是，则当前最大值成为全局最大值。3 大于 2，因此 3 也成为全局最大值。

然后我们对 -2 重复上述步骤。比较 -2 和 3 + (-2)，我们发现 1 更大，因此 1 成为当前最大值。由于 1 不大于全局最大值，所以全局最大值保持不变。

现在我们来看第 3 个元素。当前最大值要么是 3，要么是 3 加上之前的当前最大值，也就是 1。这使得 4 成为当前最大值，并且由于 4 大于现有的全局最大值，因此它成为新的全局最大值。

最后，我们来到了最后一个元素 2。卡丹算法指出，最大值要么是元素本身，要么是元素加上之前的最大值（这解释了为什么快速浏览数组后认为 [3,2] 是最大子数组是不正确的）。在这个例子中，我们比较的是 2 是否大于 2 + 4，也就是 6。6 更大，所以它成为新的当前最大值。6 也大于之前的全局最大值，所以它也是全局最大值。

没有更多元素需要检查，因此该算法将返回 6 作为全局最大值。

JavaScript 中的 Kadane 算法

为了编写这个算法，我们需要存储两个变量，分别用于保存当前最大值和全局最大值。我们还需要遍历数组并对每个元素进行检查。最后，我们将返回全局最大值。

首先，我们初始化当前最大值和全局最大值，将其设置为输入数组中的第一个元素。这样做是因为第一个元素没有前面的元素可供比较。

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  //...
}

接下来，从索引为 1 的元素开始，遍历输入数组的末尾，我们将对每个元素进行检查。为此，我们将使用 for 循环。

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  for (let i = 1; i < nums.length; i++) {
    //...
  }
  //...
}

现在，我们想看看当前元素是否nums[i]大于当前元素与前一个子数组元素之和maxCurrent + nums[i]。这里可以使用 Math.max() 函数，它会返回较大的值。较大的值将成为新的元素maxCurrent。

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  for (let i = 1; i < nums.length; i++) {
    maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
    //...
  }
  //...
}

现在我们已经找到了以当前元素结尾的最大子数组，接下来需要检查它是否大于全局最大值。如果大于，它将成为新的全局最大值。

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  for (let i = 1; i < nums.length; i++) {
    maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
    if (maxCurrent > maxGlobal) {
      maxGlobal = maxCurrent;
    }
  }
  //...
}

当 for 循环结束后，所有元素都已检查完毕，我们可以返回全局最大值。

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  for (let i = 1; i < nums.length; i++) {
    maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
    if (maxCurrent > maxGlobal) {
      maxGlobal = maxCurrent;
    }
  }
  return maxGlobal
}

就是这样！如果您有任何问题，或者有其他解决这个问题的方法，请在评论区告诉我。