最大子数组问题（Kadane算法解法）- LeetCode题目解析

咱们先聊聊这个经典的最大子数组问题：给定一个整数数组，找出其中和最大的连续子数组，返回这个最大和。这里要注意，子数组必须是连续的，可不是随便挑元素的子序列哦。

测试用例逐一分析 #

我把给定的几个测试用例和对应的预期结果列出来，方便你对照理解：

• 测试用例1: [-2,1,-3,4,-1,2,1,-5,4] → 最大连续子数组是[4,-1,2,1]，和为6
• 测试用例2: [-2, -1] → 全负数的情况，选最大的那个元素[-1]，和为-1
• 测试用例3: [-2, 1] → 最大子数组是[1]，和为1
• 测试用例4: [1] → 只有一个元素，直接返回1
• 测试用例5: [1, 2] → 整个数组就是最大子数组，和为3

Kadane算法的JavaScript实现分析 #

先看看你给出的这段代码：

function maxSubarray(array) {
  var currentMax = array[0];
  var max = array[0];
  for (var i = 0; i < array.length; i++) {
    // 比较0与currentMax + array[i]
    // 若结果小于0，则重置为0
    // 若结果大于0，则取值为currentMax + 下一个元素
    currentMax = Math.max(array[i], currentMax + array[i]);
    // 比较max与currentMax的值，选取较大者...
  }
}

先讲Kadane算法的核心逻辑 #

这个算法的思路特别巧妙：遍历数组时，我们维护两个关键变量：

• currentMax：表示以当前遍历到的元素结尾的最大子数组和
• max：表示遍历到目前为止，整个数组里的全局最大子数组和

简单说就是，每遇到一个新元素，我们要做的选择是：要么把这个元素加入之前的子数组（这样和就是currentMax + array[i]），要么干脆以这个元素为起点重新开一个子数组（和就是array[i]），选两者里大的那个更新currentMax。然后再用currentMax去更新全局的max。

原代码里的几个问题 #

你仔细看这段代码，会发现几个明显的bug：

1. 循环起始索引错了：currentMax和max已经初始化是array[0]了，结果循环从i=0开始，相当于重复处理了第一个元素，完全没必要，应该从i=1开始遍历剩下的元素。
2. 漏掉了全局max的更新：注释里写了要比较max和currentMax取较大值，但代码里根本没这一行！这会导致max一直停留在初始的array[0]，完全没更新。
3. 没有返回结果：函数最后没写return max;，调用这个函数根本拿不到任何输出。

修正后的完整代码 #

我把这些问题修复后，代码就正常工作了：

function maxSubarray(array) {
  // 加个空数组判断，虽然题目里说数组非空，但让代码更健壮
  if (array.length === 0) return 0;
  
  var currentMax = array[0];
  var max = array[0];
  
  // 从第二个元素开始遍历
  for (var i = 1; i < array.length; i++) {
    // Kadane核心逻辑：选择延续子数组或重新开始
    currentMax = Math.max(array[i], currentMax + array[i]);
    // 更新全局最大和
    max = Math.max(max, currentMax);
  }
  
  return max;
}

咱们拿第一个测试用例跑一遍验证下：

• 初始currentMax = -2，max = -2
• i=1（元素1）：Math.max(1, -2+1=-1) → 1，currentMax=1；max更新为Math.max(-2,1)=1
• i=2（元素-3）：Math.max(-3,1+(-3)=-2) → -2，currentMax=-2；max还是1
• i=3（元素4）：Math.max(4, -2+4=2) →4，currentMax=4；max更新为4
• i=4（元素-1）：Math.max(-1,4+(-1)=3) →3，currentMax=3；max还是4
• i=5（元素2）：Math.max(2,3+2=5) →5，currentMax=5；max更新为5
• i=6（元素1）：Math.max(1,5+1=6) →6，currentMax=6；max更新为6
• i=7（元素-5）：Math.max(-5,6+(-5)=1) →1，currentMax=1；max保持6
• i=8（元素4）：Math.max(4,1+4=5) →5，currentMax=5；max还是6
• 最后返回6，完全符合预期！

全负数的情况比如[-2,-1]：

• 初始currentMax=-2，max=-2
• i=1（元素-1）：Math.max(-1, -2+(-1)=-3) →-1，currentMax=-1；max更新为Math.max(-2,-1)=-1，正确。

内容的提问来源于stack exchange，提问作者sop ian