中等LeetCode 53可逐步演示引导学习
最大子数组和
Kadane：负数要不要带
顺序扫一遍，每个位置做一次选择：把当前数接在已有子数组后面，还是从它重新开一段——取和更大的那个；同时记录历史最大值 best。
时间复杂度 O(n)空间复杂度 O(1)
题单：面试热题
题目描述
给定一个整数数组 nums（可能含负数），请找出和最大的连续子数组（至少包含一个元素），返回这个最大和。
学习目标
能定义"以 i 结尾的最大子数组和"这个状态，写出转移方程，并解释为什么不能简单跳过负数。
已完成 0 / 6 阶段
诊断
先判断：负数要不要带
[-2, 1] 的最大子数组和是 1，不是 -2；[-2, 3, -1, 2] 的最大和是 4。负数到底该不该带？
[-2, 3, -1, 2] 的最大子数组和是多少？
建议先完成当前阶段（提示 / 检查 / 自评），再进入下一步；也可以直接跳过。
解题思路
核心思想
顺序扫一遍，每个位置做一次选择：把当前数接在已有子数组后面，还是从它重新开一段——取和更大的那个；同时记录历史最大值 best。
为什么需要它
枚举所有子数组是 O(n²)。但这个问题有最优子结构：以位置 i 结尾的最大子数组和，只取决于以 i-1 结尾的情况——不用回头看更早的位置，扫描一遍就能定。
第一反应：直觉方案
两层循环枚举所有起点和终点，把所有子数组的和都算出来取最大。直观，但慢。
关键洞察
关键问题是"负数要不要带"：一段前缀和如果变成负数，它只会拖累后面的数——这时不如从当前数重新开始。所以每个位置只需要比较 cur + nums[i] 和 nums[i] 两个候选，也就是 cur = max(nums[i], cur + nums[i])。这不是朴素地"跳过负数"（[-2, 1] 的最优答案是 1 而不是 -2），而是让定义自然给出答案：cur 的含义是"以当前位置结尾的最大和"，重新开始这个选项已经内含其中。
时间复杂度 O(n)空间复杂度 O(1)
易错点
- cur 的定义是"以当前位置结尾的最大和"，不是"当前见过的最大和"（那是 best）
- cur = max(nums[i], cur + nums[i])，不是 cur = max(cur, cur + nums[i])
- 全负数数组也要正确返回最大的那个负数——初始化用 nums[0]，不是 0
逐步演示
参考代码
1function maxSubArray(nums) {
2 let cur = nums[0];
3 let best = nums[0];
4 for (let i = 1; i < nums.length; i++) {
5 cur = Math.max(nums[i], cur + nums[i]);
6 best = Math.max(best, cur);
7 }
8 return best;
9}
效果图
预测：答对 0 / 共 1 题
第 1 / 11 步