前言LeetCode 第 53 题 “最大子数组和” 是算法入门的经典题目几乎所有学习算法的同学都会遇到它。这道题有多种解法从暴力枚举的 O (n²) 到分治法的 O (nlogn)再到最优的 O (n) 动态规划和贪心算法。很多同学在学习贪心解法时会看到一种非常简洁的写法但同时也会产生很多疑问为什么要先更新最大值再重置计数器为什么计数器小于等于 0 才重置全负数的情况会不会出错今天我们就来深度拆解这个极简贪心解法把所有你可能遇到的疑问点一次性讲透。一、问题回顾给你一个整数数组nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。示例输入nums [-2,1,-3,4,-1,2,1,-5,4]输出6解释连续子数组[4,-1,2,1]的和最大为 6。二、你的解法代码先把我们今天要分析的代码贴出来cpp运行class Solution { public: int maxSubArray(vectorint nums) { int result INT32_MIN; // 记录全局最大和 int count 0; // 记录当前子数组的和 for (int i 0; i nums.size(); i) { count nums[i]; // 累加当前元素到当前子数组 if (result count) { // 如果当前子数组和更大更新全局最大值 result count; } if (count 0) { // 如果当前子数组和小于等于0重置计数器 count 0; } } return result; } };这个代码非常简洁只有十几行时间复杂度 O (n)空间复杂度 O (1)是理论上最优的解法。但正是因为它太简洁了很多细节容易被忽略从而产生疑问。三、逐行代码解析我们先把代码的每一步做什么讲清楚初始化result INT32_MIN全局最大和初始化为整数的最小值确保任何一个元素都能比它大。count 0当前子数组的和初始化为 0。遍历数组count nums[i]把当前元素加到当前子数组的和中。if (result count) result count比较当前子数组的和与全局最大值如果更大就更新。if (count 0) count 0如果当前子数组的和小于等于 0说明这个子数组对后面的元素没有任何贡献直接抛弃从下一个元素重新开始计算。四、核心疑问点深度解答这是本文的重点我们来逐一解答大家最常遇到的疑问。疑问 1为什么先更新result再重置count顺序能不能反过来这是最关键的一个问题也是最容易出错的地方。答案绝对不能反过来我们用一个极端例子来验证nums [-3, -1, -2]全负数数组。正确顺序先更新再重置的执行过程i0: count 0 (-3) -3 → result max(INT_MIN, -3) -3 → count 0 → count0i1: count 0 (-1) -1 → result max(-3, -1) -1 → count 0 → count0i2: count 0 (-2) -2 → result max(-1, -2) -1 → count 0 → count0返回结果-1正确最大子数组是 [-1]错误顺序先重置再更新的执行过程i0: count 0 (-3) -3 → count 0 → count0 → result max(INT_MIN, 0) 0i1: count 0 (-1) -1 → count 0 → count0 → result max(0, 0) 0i2: count 0 (-2) -2 → count 0 → count0 → result max(0, 0) 0返回结果0错误数组中没有 0 这个元素原因当当前子数组和为负数时我们需要先把这个负数记录到result中因为它可能是目前最大的然后再重置count。如果先重置就会丢失这个负数导致全负数数组返回错误的 0。疑问 2为什么是count 0才重置等于 0 的时候重置会不会有问题答案等于 0 的时候重置是完全正确的甚至是更优的选择。我们来分析两种情况count 0当前子数组和为负数显然对后面的元素没有贡献。比如前面的和是 - 2后面加一个 5结果是 3但如果直接从 5 开始结果是 5显然更大。count 0当前子数组和为 0对后面的元素没有贡献也没有损害。比如前面的和是 0后面加一个 5结果是 5直接从 5 开始结果也是 5。既然结果一样那为什么不重置呢重置count为 0 可以让代码更简洁而且不会影响结果。反例验证如果我们把条件改成count 0代码也能通过所有测试用例只是在count0的时候会继续累加多做了一些无用功。疑问 3为什么result初始化为INT32_MIN而不是 0答案为了处理全负数数组的情况。如果result初始化为 0那么在全负数数组的情况下result永远不会被更新最终返回 0这显然是错误的如前面的例子[-3,-1,-2]。而初始化为INT32_MIN可以保证数组中的第一个元素无论正负都会被正确记录到result中。疑问 4这个算法为什么是贪心算法贪心的选择是什么答案这个算法的贪心选择是如果当前子数组的和大于 0就继续扩展如果小于等于 0就抛弃它从下一个元素重新开始。贪心算法的核心是 “局部最优导致全局最优”。在这个问题中我们的局部最优选择是对于每一个位置我们只保留以该位置结尾的、和最大的子数组。为什么这个局部最优能导致全局最优因为如果一个子数组的和是负数那么它后面的任何元素加上这个子数组都不如直接从后面的元素开始。疑问 5这个写法和标准的count max(nums[i], count nums[i])写法有什么区别很多教材和题解中会给出这样的标准贪心写法cpp运行class Solution { public: int maxSubArray(vectorint nums) { int result nums[0]; int count nums[0]; for (int i 1; i nums.size(); i) { count max(nums[i], count nums[i]); // 选“单独开始”还是“接在前面” result max(result, count); } return result; } };答案这两种写法本质上是完全等价的只是实现方式不同。我们来证明一下当count nums[i] nums[i]时等价于count 0此时你的代码会执行count nums[i]和标准写法一致。当count nums[i] nums[i]时等价于count 0此时你的代码会先执行count nums[i]然后重置count 0。这和标准写法中count nums[i]有什么区别吗其实没有区别因为在下一次循环中你的代码会执行count nums[i1]也就是0 nums[i1]而标准写法会执行count max(nums[i1], nums[i] nums[i1])。哦等一下这里好像有个区别让我们用例子来验证数组[2, -2, 3]你的代码执行过程i0: count2 → result2 → count0 → 不重置i1: count0 → resultmax(2,0)2 → count0 → count0i2: count3 → resultmax (2,3)3 → 返回 3标准写法执行过程i0: count2 → result2i1: countmax(-2, 2-20) → 0 → resultmax(2,0)2i2: countmax (3, 033) → 3 → resultmax (2,3)3 → 返回 3结果完全一样再试一个全负数的例子数组[-3, -1, -2]你的代码执行过程i0: count-3 → result-3 → count0 → count0i1: count-1 → result-1 → count0 → count0i2: count-2 → result-1 → 返回 - 1标准写法执行过程i0: count-3 → result-3i1: countmax(-1, -3-1-4) → -1 → result-1i2: countmax (-2, -1-2-3) → -2 → result-1 → 返回 - 1结果还是完全一样结论你的写法和标准写法在数学上是等价的只是你的写法用了一个巧妙的重置技巧让代码看起来更简洁。疑问 6如果数组中有 0这个算法能正确处理吗答案完全可以。我们用例子验证数组[-2, 0, -1]你的代码执行过程i0: count-2 → result-2 → count0 → count0i1: count0 → resultmax(-2,0)0 → count0 → count0i2: count-1 → resultmax (0,-1)0 → 返回 0正确最大子数组是 [0]五、边界情况测试为了确保代码的正确性我们来测试所有可能的边界情况表格测试用例输入预期输出你的代码输出结果单元素正数[5]55✅单元素负数[-5]-5-5✅全正数[1,2,3,4]1010✅全负数[-3,-1,-2]-1-1✅包含 0[-2,0,-1]00✅混合正负[-2,1,-3,4,-1,2,1,-5,4]66✅末尾最大[1,-2,3,4]77✅开头最大[5,4,-1,-7,-8]99✅所有测试用例都通过证明你的代码是完全正确的。六、算法复杂度分析时间复杂度O (n)只需要遍历数组一次。空间复杂度O (1)只使用了两个变量没有额外的空间开销。这是解决这个问题的理论最优复杂度没有比这更好的解法了。七、总结你提供的这个最大子数组和的贪心解法是一个非常优秀的实现。它不仅简洁高效而且逻辑严谨能够正确处理所有边界情况。我们今天解答了最常见的 6 个疑问点核心要点总结如下顺序不能反必须先更新result再重置count否则全负数数组会出错。重置条件正确count 0时重置是最优选择不会影响结果。初始值要正确result必须初始化为INT32_MIN不能是 0。等价于标准写法你的写法和count max(nums[i], count nums[i])写法本质上是一样的。这个算法虽然简单但其中蕴含的贪心思想非常重要很多更复杂的算法问题都可以用类似的思路来解决。
今日算法（贪心找子数组）
前言LeetCode 第 53 题 “最大子数组和” 是算法入门的经典题目几乎所有学习算法的同学都会遇到它。这道题有多种解法从暴力枚举的 O (n²) 到分治法的 O (nlogn)再到最优的 O (n) 动态规划和贪心算法。很多同学在学习贪心解法时会看到一种非常简洁的写法但同时也会产生很多疑问为什么要先更新最大值再重置计数器为什么计数器小于等于 0 才重置全负数的情况会不会出错今天我们就来深度拆解这个极简贪心解法把所有你可能遇到的疑问点一次性讲透。一、问题回顾给你一个整数数组nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。示例输入nums [-2,1,-3,4,-1,2,1,-5,4]输出6解释连续子数组[4,-1,2,1]的和最大为 6。二、你的解法代码先把我们今天要分析的代码贴出来cpp运行class Solution { public: int maxSubArray(vectorint nums) { int result INT32_MIN; // 记录全局最大和 int count 0; // 记录当前子数组的和 for (int i 0; i nums.size(); i) { count nums[i]; // 累加当前元素到当前子数组 if (result count) { // 如果当前子数组和更大更新全局最大值 result count; } if (count 0) { // 如果当前子数组和小于等于0重置计数器 count 0; } } return result; } };这个代码非常简洁只有十几行时间复杂度 O (n)空间复杂度 O (1)是理论上最优的解法。但正是因为它太简洁了很多细节容易被忽略从而产生疑问。三、逐行代码解析我们先把代码的每一步做什么讲清楚初始化result INT32_MIN全局最大和初始化为整数的最小值确保任何一个元素都能比它大。count 0当前子数组的和初始化为 0。遍历数组count nums[i]把当前元素加到当前子数组的和中。if (result count) result count比较当前子数组的和与全局最大值如果更大就更新。if (count 0) count 0如果当前子数组的和小于等于 0说明这个子数组对后面的元素没有任何贡献直接抛弃从下一个元素重新开始计算。四、核心疑问点深度解答这是本文的重点我们来逐一解答大家最常遇到的疑问。疑问 1为什么先更新result再重置count顺序能不能反过来这是最关键的一个问题也是最容易出错的地方。答案绝对不能反过来我们用一个极端例子来验证nums [-3, -1, -2]全负数数组。正确顺序先更新再重置的执行过程i0: count 0 (-3) -3 → result max(INT_MIN, -3) -3 → count 0 → count0i1: count 0 (-1) -1 → result max(-3, -1) -1 → count 0 → count0i2: count 0 (-2) -2 → result max(-1, -2) -1 → count 0 → count0返回结果-1正确最大子数组是 [-1]错误顺序先重置再更新的执行过程i0: count 0 (-3) -3 → count 0 → count0 → result max(INT_MIN, 0) 0i1: count 0 (-1) -1 → count 0 → count0 → result max(0, 0) 0i2: count 0 (-2) -2 → count 0 → count0 → result max(0, 0) 0返回结果0错误数组中没有 0 这个元素原因当当前子数组和为负数时我们需要先把这个负数记录到result中因为它可能是目前最大的然后再重置count。如果先重置就会丢失这个负数导致全负数数组返回错误的 0。疑问 2为什么是count 0才重置等于 0 的时候重置会不会有问题答案等于 0 的时候重置是完全正确的甚至是更优的选择。我们来分析两种情况count 0当前子数组和为负数显然对后面的元素没有贡献。比如前面的和是 - 2后面加一个 5结果是 3但如果直接从 5 开始结果是 5显然更大。count 0当前子数组和为 0对后面的元素没有贡献也没有损害。比如前面的和是 0后面加一个 5结果是 5直接从 5 开始结果也是 5。既然结果一样那为什么不重置呢重置count为 0 可以让代码更简洁而且不会影响结果。反例验证如果我们把条件改成count 0代码也能通过所有测试用例只是在count0的时候会继续累加多做了一些无用功。疑问 3为什么result初始化为INT32_MIN而不是 0答案为了处理全负数数组的情况。如果result初始化为 0那么在全负数数组的情况下result永远不会被更新最终返回 0这显然是错误的如前面的例子[-3,-1,-2]。而初始化为INT32_MIN可以保证数组中的第一个元素无论正负都会被正确记录到result中。疑问 4这个算法为什么是贪心算法贪心的选择是什么答案这个算法的贪心选择是如果当前子数组的和大于 0就继续扩展如果小于等于 0就抛弃它从下一个元素重新开始。贪心算法的核心是 “局部最优导致全局最优”。在这个问题中我们的局部最优选择是对于每一个位置我们只保留以该位置结尾的、和最大的子数组。为什么这个局部最优能导致全局最优因为如果一个子数组的和是负数那么它后面的任何元素加上这个子数组都不如直接从后面的元素开始。疑问 5这个写法和标准的count max(nums[i], count nums[i])写法有什么区别很多教材和题解中会给出这样的标准贪心写法cpp运行class Solution { public: int maxSubArray(vectorint nums) { int result nums[0]; int count nums[0]; for (int i 1; i nums.size(); i) { count max(nums[i], count nums[i]); // 选“单独开始”还是“接在前面” result max(result, count); } return result; } };答案这两种写法本质上是完全等价的只是实现方式不同。我们来证明一下当count nums[i] nums[i]时等价于count 0此时你的代码会执行count nums[i]和标准写法一致。当count nums[i] nums[i]时等价于count 0此时你的代码会先执行count nums[i]然后重置count 0。这和标准写法中count nums[i]有什么区别吗其实没有区别因为在下一次循环中你的代码会执行count nums[i1]也就是0 nums[i1]而标准写法会执行count max(nums[i1], nums[i] nums[i1])。哦等一下这里好像有个区别让我们用例子来验证数组[2, -2, 3]你的代码执行过程i0: count2 → result2 → count0 → 不重置i1: count0 → resultmax(2,0)2 → count0 → count0i2: count3 → resultmax (2,3)3 → 返回 3标准写法执行过程i0: count2 → result2i1: countmax(-2, 2-20) → 0 → resultmax(2,0)2i2: countmax (3, 033) → 3 → resultmax (2,3)3 → 返回 3结果完全一样再试一个全负数的例子数组[-3, -1, -2]你的代码执行过程i0: count-3 → result-3 → count0 → count0i1: count-1 → result-1 → count0 → count0i2: count-2 → result-1 → 返回 - 1标准写法执行过程i0: count-3 → result-3i1: countmax(-1, -3-1-4) → -1 → result-1i2: countmax (-2, -1-2-3) → -2 → result-1 → 返回 - 1结果还是完全一样结论你的写法和标准写法在数学上是等价的只是你的写法用了一个巧妙的重置技巧让代码看起来更简洁。疑问 6如果数组中有 0这个算法能正确处理吗答案完全可以。我们用例子验证数组[-2, 0, -1]你的代码执行过程i0: count-2 → result-2 → count0 → count0i1: count0 → resultmax(-2,0)0 → count0 → count0i2: count-1 → resultmax (0,-1)0 → 返回 0正确最大子数组是 [0]五、边界情况测试为了确保代码的正确性我们来测试所有可能的边界情况表格测试用例输入预期输出你的代码输出结果单元素正数[5]55✅单元素负数[-5]-5-5✅全正数[1,2,3,4]1010✅全负数[-3,-1,-2]-1-1✅包含 0[-2,0,-1]00✅混合正负[-2,1,-3,4,-1,2,1,-5,4]66✅末尾最大[1,-2,3,4]77✅开头最大[5,4,-1,-7,-8]99✅所有测试用例都通过证明你的代码是完全正确的。六、算法复杂度分析时间复杂度O (n)只需要遍历数组一次。空间复杂度O (1)只使用了两个变量没有额外的空间开销。这是解决这个问题的理论最优复杂度没有比这更好的解法了。七、总结你提供的这个最大子数组和的贪心解法是一个非常优秀的实现。它不仅简洁高效而且逻辑严谨能够正确处理所有边界情况。我们今天解答了最常见的 6 个疑问点核心要点总结如下顺序不能反必须先更新result再重置count否则全负数数组会出错。重置条件正确count 0时重置是最优选择不会影响结果。初始值要正确result必须初始化为INT32_MIN不能是 0。等价于标准写法你的写法和count max(nums[i], count nums[i])写法本质上是一样的。这个算法虽然简单但其中蕴含的贪心思想非常重要很多更复杂的算法问题都可以用类似的思路来解决。
