LeetCode 53. 最大子数组和

题目核心

给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6

输入：nums = [5,4,-1,7,8]
输出：23（整个数组）

输入：nums = [-1]
输出：-1

注意：子数组要求连续，而且元素可能全为负数，此时答案是"最不差的那个负数"。

解题思考过程

第一步：暴力枚举

枚举所有起点和终点并累加：

时间复杂度：O(n²)
空间复杂度：O(1)

还能更优。

第二步：核心抉择——前面的和为负，还要不要带着？

假设当前处理到 nums[i]，以 i-1 结尾的最优子数组和是 prev：

• 如果 prev > 0：带着它，prev + nums[i] 比单干大。
• 如果 prev ≤ 0：它只会"拖后腿"，不如从 nums[i] 重新开始。

所以：

f(i) = max(f(i-1) + nums[i], nums[i])

其中 f(i) 表示以 i 结尾的最大子数组和。这就是 Kadane 算法的状态转移。

最终答案是 max(f(i))——和 300 题一样，最优子数组可能在任意位置结尾。

第三步：空间压缩

f(i) 只依赖 f(i-1)，不需要 dp 数组，一个滚动变量 prev 就够了：

时间复杂度：O(n)
空间复杂度：O(1)

当前解法：Kadane（滚动变量）

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let ans = -Infinity;
  let prev = -Infinity;

  for (let i = 0; i < nums.length; i++) {
    // 以 i 结尾：要么接上前面，要么从 i 重新开始
    prev = Math.max(prev + nums[i], nums[i]);

    // 全局答案在所有"以 i 结尾"里取最大
    ans = Math.max(prev, ans);
  }

  return ans;
};

代码逐行解释

初始值

let ans = -Infinity;
let prev = -Infinity;

• ans 是全局最大和。不能初始化成 0：数组全负时，0 会被错误地当成答案（比如 [-1] 应返回 -1）。
• prev 表示以当前位置结尾的最大和。

第一轮 i=0 时：

Math.max(-Infinity + nums[0], nums[0]) = Math.max(-Infinity, nums[0]) = nums[0]

所以 -Infinity 的初值在首轮恰好收敛为 nums[0]，结果正确。（更常规的写法是 prev = ans = nums[0]，循环从 1 开始，少一次对 -Infinity 的依赖。）

状态转移

prev = Math.max(prev + nums[i], nums[i]);

• prev + nums[i]：延续前一段。
• nums[i]：抛弃负资产，重起炉灶。

二选一，对应当前结尾的最优。

更新全局答案

ans = Math.max(prev, ans);

每轮都要比较：prev 只保证"以 i 结尾"最优，全局最优可能出现在更早的位置。

执行过程示例

以 nums = [-2,1,-3,4,-1,2,1,-5,4] 为例：

 i  nums[i]  prev（以 i 结尾的最大和）   ans
 0   -2      -2                          -2
 1    1      max(-2+1, 1) = 1             1
 2   -3      max(1-3, -3) = -2            1
 3    4      max(-2+4, 4) = 4             4
 4   -1      max(4-1, -1) = 3             4
 5    2      max(3+2, 2)  = 5             5
 6    1      max(5+1, 1)  = 6             6   ← [4,-1,2,1]
 7   -5      max(6-5, -5) = 1             6
 8    4      max(1+4, 4)  = 5             6

答案 6

复杂度分析

时间复杂度：O(n) — 一次遍历
空间复杂度：O(1) — 只用两个变量

替代写法一：dp 数组版

状态定义写全，方便理解后再压缩：

var maxSubArray = function (nums) {
  const dp = new Array(nums.length);
  dp[0] = nums[0];
  let ans = dp[0];

  for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
    ans = Math.max(ans, dp[i]);
  }

  return ans;
};

时间 O(n)，空间 O(n)；滚动变量版就是把 dp[i-1] 换成 prev。

替代写法二：分治

区间 [l, r) 的最大子数组和要么完全在左半、要么完全在右半、要么跨过中点（用两侧最大后缀 + 最大前缀计算），递归合并：

时间复杂度：O(n log n)
空间复杂度：O(log n)

复杂度不如 Kadane，但它是理解"区间信息如何合并"的经典题，线段树式的状态还能扩展成动态查询。

易错点

1. ans 初始化成 0：全负数组必错。用 -Infinity 或 nums[0]。

2. 只更新 prev 不取全局 max：直接返回最后一个 prev 等价于假设最优子数组一定在末尾结尾，不成立。

3. 你贴的原始代码里有一段从未被调用的 dfs（死代码）：

   const dfs = (nums, i, mem) => {
     if (i < 0) return 0;
     let res = 0;
     res = Math.max(dfs(nums, i - 1, mem) + nums[i], nums[i]);
     return res;
   };

   真正出答案的是下面的迭代循环，这段函数定义后从未调用，提交前应删掉。另外它即使被调用，语义上也只返回"以 i 结尾"的那一个值，仍需要外层对所有 i 取 max 才是本题答案。

4. "负数就重开"不要误记成"遇到负数就重开"：决定取舍的是前缀和 prev 是否为正，不是当前元素的正负——-1 接在和为 6 的段后依然值得保留。