LeetCode 53.最大子数组和：贪心算法下的连续子数组最优解
一、问题定义与核心挑战
1.1 问题描述
给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
1.2 核心特征与难点
- 子数组连续性：必须是原数组中连续的元素组成（与子序列不同）
- 存在负数：数组中可能包含负数，增加了选择的复杂性（不能简单累加所有元素）
- 最优子结构：最大子数组可能存在于数组的任意位置，需要高效定位
示例：
- 输入：
nums = [-2,1,-3,4,-1,2,1,-5,4] - 输出：
6（对应子数组[4,-1,2,1]，和为6）
二、解题思路：贪心算法的局部最优到全局最优
2.1 核心思想
贪心算法的关键在于做出当前状态下的最优选择，并通过局部最优积累全局最优。对于本题：
- 局部最优：若当前累加和为负数，继续累加会拖累后续子数组的和，因此应重置累加和（从下一个元素重新开始计算）
- 全局最优：在遍历过程中，始终记录最大的累加和，即为最大子数组和
2.2 直观理解
可以将数组想象成一段起伏的路线，累加和是当前的海拔高度：
- 当海拔为正时，继续前进可能达到更高海拔（保留当前累加和）
- 当海拔为负时，继续前进只会更低，不如重新从当前位置出发（重置累加和）
- 全程记录遇到的最高海拔，即为结果
三、代码逐行解析
3.1 初始化变量
int max = Integer.MIN_VALUE; // 存储全局最大和，初始化为最小值避免负数场景出错
int cnt = 0; // 存储当前子数组的累加和
3.2 遍历数组计算
for (int i = 0; i < nums.length; i++) {cnt += nums[i]; // 累加当前元素到子数组和中// 更新全局最大值：比较当前子数组和与历史最大值max = Math.max(cnt, max);// 贪心决策：若当前累加和为负，重置为0（从下一个元素重新开始）if (cnt <= 0) {cnt = 0;}
}
3.3 返回结果
return max; // 全局最大子数组和
四、算法执行过程演示
以示例 nums = [-2,1,-3,4,-1,2,1,-5,4] 为例，分步解析：
索引 i | 当前元素 nums[i] | cnt 变化 | max 变化 | 操作说明 |
|---|---|---|---|---|
| 0 | -2 | 0 + (-2) = -2 | max(-∞, -2) = -2 | cnt ≤0 → 重置为0 |
| 1 | 1 | 0 + 1 = 1 | max(-2, 1) = 1 | cnt 为正 → 保留 |
| 2 | -3 | 1 + (-3) = -2 | max(1, -2) = 1 | cnt ≤0 → 重置为0 |
| 3 | 4 | 0 + 4 = 4 | max(1, 4) = 4 | cnt 为正 → 保留 |
| 4 | -1 | 4 + (-1) = 3 | max(4, 3) = 4 | cnt 为正 → 保留 |
| 5 | 2 | 3 + 2 = 5 | max(4, 5) = 5 | cnt 为正 → 保留 |
| 6 | 1 | 5 + 1 = 6 | max(5, 6) = 6 | cnt 为正 → 保留 |
| 7 | -5 | 6 + (-5) = 1 | max(6, 1) = 6 | cnt 为正 → 保留 |
| 8 | 4 | 1 + 4 = 5 | max(6, 5) = 6 | 循环结束 |
最终结果为 6，与预期一致。
五、核心逻辑深度解析
5.1 为什么重置累加和？
当 cnt ≤ 0 时，说明当前子数组的和已经是负数或零，继续带着这个和计算后续元素：
- 若后续元素为正数，加上负数会比直接从该正数开始计算更小
- 若后续元素为负数，加上负数会变得更小
- 因此重置为0（相当于从下一个元素重新开始计算子数组和）是局部最优选择
5.2 为什么不需要记录子数组的起止位置？
题目只要求返回最大和，无需知道具体子数组的位置，因此只需通过 max 变量跟踪最大值即可，节省空间。
5.3 全负数场景的处理
当数组全为负数时（如 [-3, -1, -2]）：
- 每次累加后
cnt都是负数，会被重置 - 但
max会在每次累加后更新，最终保留最大的那个负数（即数组中最大的元素） - 符合“子数组最少包含一个元素”的要求
六、算法复杂度分析
- 时间复杂度：
O(n)，仅需遍历数组一次（n为数组长度） - 空间复杂度：
O(1)，仅使用常数个变量（max和cnt），与输入规模无关
七、常见误区与优化说明
7.1 误区1：初始值设置错误
若将 max 初始化为0，当数组全为负数时，会错误返回0（正确结果应为最大的负数）。因此必须初始化为 Integer.MIN_VALUE。
7.2 误区2：重置条件判断错误
若将重置条件设为 cnt < 0（而非 cnt ≤ 0），当 cnt = 0 时不会重置，可能导致后续计算包含无意义的0（如数组 [0, -1] 会得到0，虽然结果正确，但逻辑不够严谨）。
7.3 与动态规划的关联
本题也可用动态规划求解（dp[i] = max(nums[i], dp[i-1] + nums[i])），但贪心算法更简洁，空间效率更高（动态规划若不优化空间为 O(n)）。两种算法本质都是判断“是否保留之前的累加和”。
八、总结：贪心算法的适用场景
本题的贪心解法体现了“局部最优推导全局最优”的核心思想，适用于以下场景：
- 问题可分解为一系列局部决策
- 每个局部决策的最优选择能累积成全局最优
- 无需回溯（每个决策一旦做出就不再修改）
最大子数组和问题通过简单的累加、比较、重置操作，在 linear 时间内解决，是贪心算法高效性的典型体现。掌握这种思路，可解决类似的连续序列优化问题（如最大乘积子数组等）。