复盘 · LC 53 最大子数组和

题目

• 题号：LeetCode 53
• 名称：最大子数组和（Maximum Subarray）
• 难度：Medium
• 链接：leetcode.cn/problems/maximum-subarray
• 今日代码：53-最大子数组和/index.js

题意

给整数数组 nums，找一个连续子数组，使其元素和最大，返回这个最大和。

• 子数组至少含 1 个元素（不能交空段）。
• 数组可含负数；全为负时答案是「最大的那个负数」。

边界：[-1] → -1；[-2,1,-3,4,-1,2,1,-5,4] → 6（[4,-1,2,1]）；单元素、全正、全负。

涉及算法

标签	一句话
Kadane / 贪心	扫到每位时：要么接上一段，要么从当前重新开段
一维 DP	dp[i] = max(nums[i], dp[i-1] + nums[i])，答案取 max(dp)

教程对照：一维状态转移见 21 · DP 入门一维；本题是「以 i 结尾的最大和」模板，面试常叫 Kadane。

评价我的解法

思路：累加 curSum，一旦变负就清零重新开段；另用 curMaxNum 兜底「全负数」。本质是 Kadane 的变体，210/210 通过，且跑分不错（约 1ms）。

我的代码（摘自 53-最大子数组和/index.js，不含测例）：

var maxSubArray = function (nums) {
  let res = -(10 ** 5);
  let curSum = 0;
  let curMaxNum = -(10 ** 5);
  for (let i = 0; i < nums.length; i++) {
    const curNum = nums[i];
    curMaxNum = Math.max(curMaxNum, curNum);
    curSum += curNum;
    if (curSum < 0) {
      curSum = 0;
    }
    if (curMaxNum >= 0) {
      res = Math.max(res, curSum);
    } else {
      res = Math.max(res, curMaxNum);
    }
  }
  return res;
};

对在哪：

1. 「负前缀丢掉」直觉正确：和为负的前缀不可能帮后面的段变大，清零再开等价于标准转移里「不接上一段」。
2. 全负分支意识到了：本地测例 [-1] 说明你知道「不能一直用 0」。

糙在哪：

1. 两套答案逻辑：curMaxNum >= 0 时用 curSum，否则用全局最大元素。标准 Kadane 用一条转移同时覆盖全负，不必分岔。
2. 魔法初值 -(10 ** 5)：依赖题面 nums[i] ≥ -10^4 才安全；可读性差，面试更干净的是 res = nums[0] 或 -Infinity。
3. curSum 语义飘：清零后 curSum === 0 表示「空段」，但题目不允许空子数组——靠「有非负元素才更新 res」和「全负走 curMaxNum」两套补丁拼正确性，口述费劲。
4. 注释里的「我太牛逼了」可以留着庆祝，但复盘要认：AC ≠ 模板最干净。

小结：能独立 AC Medium 数组经典题，加分。下一步把「负则清零 + 全负特判」收成一句转移：cur = max(x, cur + x)。

最佳题解

推荐写法（标准 Kadane，一条链）：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let cur = nums[0];
  let ans = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    ans = Math.max(ans, cur);
  }
  return ans;
};

• 时间 O(n)，空间 O(1)。
• 为何更优：cur 明确表示「以当前下标结尾的最大子段和」；全负时 cur 始终是某个元素本身，无需第二套分支；初始化用真实元素，不靠题面下界。

关联题目

题	为何相关
152. 乘积最大子数组	同「以 i 结尾」；乘积要兼顾负负得正
918. 环形子数组的最大和	53 的环形版：最大 = 普通最大 / 总和减最小
121. 买卖股票的最佳时机	一遍扫维护「历史最优」同类手感（你 7/24 做过）

一句话带走

最大子数组和：cur = max(x, cur+x)，全程取 max(cur)；别用「清零 + 全负特判」两套逻辑硬拼。