LeetCode 152 最大乘积子数组Maximum Product SubarrayKadane 双状态动态规划题解【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 LeetCode 152「最大乘积子数组」Maximum Product Subarray展开以本仓库 hints/maximum-product-subarray.md 给出的复杂度目标与解题提示为主线结合 articles/maximum-product-subarray.md 的完整题解与各语言源码实现讲解从暴力枚举到 Kadane 风格双状态动态规划的完整推导路径。读完本文你将掌握为何求乘积的最大子数组不能照搬最大子数组和的单状态 DP、如何用curMax与curMin两个状态解决负数翻转问题以及零值拆分、前缀/后缀扫描等工程化技巧。问题定义与复杂度目标给定一个整数数组nums要求找出数组中乘积最大的连续子数组并返回该乘积。题目保证结果落在 32 位整数范围内。仓库提示文档 hints/maximum-product-subarray.md 首先给出了明确的目标约束时间复杂度O(n)其中n为输入数组长度空间复杂度O(1)。也就是说最优解必须是一次线性扫描、只使用常数级额外空间的算法。以此为标尺我们可以依次评估暴力法、滑动窗口、Kadane 双状态 DP 与前缀/后缀扫描四种方案的取舍。前置知识在动手前建议先掌握以下三点见 articles/maximum-product-subarray.md 的 Prerequisites 部分动态规划 / Kadane 算法理解在单次遍历中跟踪最优子数组值的思路负数乘积的符号翻转负负得正导致只跟踪最大值不够必须同时跟踪最小值前缀/后缀累积乘积利用双向累积乘积定位最优子数组。方法一暴力枚举Brute Force思路子数组的乘积会因为两个因素发生剧烈变化负数会把当前最大值翻转为最小值反之亦然零会把乘积重置为 0。暴力法的策略是显式枚举所有可能的连续子数组固定起始下标i不断向右累乘记录过程中出现过的最大乘积。由于每个子数组都被逐一计算结果必然正确但代价高昂。算法步骤用res记录答案初始化为nums[0]对每个起始下标i令cur nums[i]并更新res对每个j i执行cur * nums[j]并更新res返回res。Python 实现来自 articles/maximum-product-subarray.mdclass Solution: def maxProduct(self, nums: List[int]) - int: res nums[0] for i in range(len(nums)): cur nums[i] res max(res, cur) for j in range(i 1, len(nums)): cur * nums[j] res max(res, cur) return res本仓库 javascript/0152-maximum-product-subarray.js 中也保留了等价的暴力实现linearSearchgetMax双层循环并在注释中标注其复杂度为Time O(N^2) | Space O(1)。复杂度时间复杂度$O(n ^ 2)$空间复杂度$O(1)$这正是提示 1 指出的方向暴力法可以正确求解但达不到 O(n) 的目标需要转向动态规划思路。方法二按零切分的滑动窗口思路最大乘积子数组问题的难点在于负数翻转符号零打断乘积。任何跨越零的子数组乘积都会被归零因此可以把数组按零切分成若干个不含零的段。在每段内部若负数个数为偶数整段乘积为正通常就是最优解若负数个数为奇数则必须丢弃从段首到第一个负数的前缀或从最后一个负数到段尾的后缀使剩余部分包含偶数个负数。这种滑动窗口思路维护一个负数个数合法偶数的窗口超出时从左端收缩。算法步骤以数组中的最大元素初始化res覆盖全为负数或全为零的情况按零切分nums为若干无零段对每段统计负数个数negs确定窗口应保留的负数个数need负数为偶数时need negs为奇数时need negs - 1用双指针j..i维护运行乘积i右扩累乘窗口内负数超过need时移动j并除掉左侧元素窗口合法时用当前prod更新res返回res。复杂度时间复杂度$O(n)$空间复杂度$O(n)$需要额外存储切分后的段该方案虽然达到线性时间但空间不符合 O(1) 要求且实现中通过除法回退乘积在含零场景下需要格外小心因此实际更推荐下面的 Kadane 双状态 DP。方法三Kadane 算法双状态动态规划——最优解思路经典的最大子数组和问题只需跟踪一个状态当前最大和。但乘积问题不行负 × 负 正一个很小的负数在乘上另一个负数后可能一跃成为最大值因此每个下标处必须同时跟踪两个值curMax以当前下标结尾的最大乘积curMin以当前下标结尾的最小乘积。curMin的价值在于当当前数字为负时num * curMin最小负数乘负数可能产生新的最大值。而零值天然被处理——因为候选值中包含num本身遇到零即可重新开始。这正是提示 2 与提示 3 的核心在引入新元素时只需维护最小、最大两个乘积值分别考虑新开子数组乘以之前的最大乘积乘以之前的最小乘积三种情况全局最大乘积单独跟踪。提示 3 明确指出这就是 Kadane 算法的变体。算法步骤初始化res nums[0]curMax 1curMin 1遍历每个num先用临时变量tmp保存curMax * num因为curMax即将被更新curMax max(num * curMax, num * curMin, num)curMin min(tmp, num * curMin, num)res max(res, curMax)返回res。多语言实现仓库各语言实现完全一致可直接对照学习。Pythonpython/0152-maximum-product-subarray.pyclass Solution: def maxProduct(self, nums: List[int]) - int: # O(n)/O(1) : Time/Memory res nums[0] curMin, curMax 1, 1 for n in nums: tmp curMax * n curMax max(n * curMax, n * curMin, n) curMin min(tmp, n * curMin, n) res max(res, curMax) return resCcpp/0152-maximum-product-subarray.cppclass Solution { public: int maxProduct(vectorint nums) { int res nums[0]; int curMin 1, curMax 1; for(int i 0; i nums.size(); i) { int n nums[i]; int tmp curMax * n; curMax max(max(n * curMax, n * curMin), n); curMin min(min(tmp, n * curMin), n); res max(res, curMax); } return res; } };Javajava/0152-maximum-product-subarray.java额外处理了单元素数组的边界情况class Solution { public int maxProduct(int[] nums) { if (nums.length 1) return nums[0]; int res nums[0]; int max 1; int min 1; for (int n : nums) { int tmp max * n; max Math.max(n, Math.max(tmp, min * n)); min Math.min(n, Math.min(tmp, min * n)); res Math.max(res, max); } return res; } }Gogo/0152-maximum-product-subarray.go需要注意 Go 标准库没有整数max/min文件中自行实现了辅助函数func maxProduct(nums []int) int { res, curMin, curMax : nums[0], 1, 1 for i : 0; i len(nums); i { temp : curMax * nums[i] curMax max(max(nums[i] * curMax, nums[i] * curMin), nums[i]) curMin min(min(temp, nums[i] * curMin), nums[i]) res max(res, curMax) } return res }Rustrust/0152-maximum-product-subarray.rs用Vec的iter().max()/iter().min()表达三者取极值并用nums.iter().max()初始化res与 Java 的单元素特判殊途同归impl Solution { pub fn max_product(nums: Veci32) - i32 { let (mut res, mut big, mut small) (*nums.iter().max().unwrap(), 1, 1); for n in nums { let tmp big; big vec![n, big * n, small * n].into_iter().max().unwrap(); small vec![n, tmp * n, small * n].into_iter().min().unwrap(); res res.max(big); } res } }复杂度时间复杂度$O(n)$空间复杂度$O(1)$完全满足提示文档设定的目标是本题的标准最优解。一次遍历正确性示例以nums [2, 3, -2, 4]为例下标numcurMax 计算curMin 计算res02max(2×1, 2×1, 2) 2min(2, 2, 2) 2213max(6, 6, 3) 6min(6, 6, 3) 362-2max(-12, -6, -2) -2min(-12, -6, -2) -12634max(-8, -48, 4) 4min(-8, -48, 4) -486注意下标 2 处curMin -12被保存下来它正是以-2结尾的最小乘积2 × 3 × -2虽然它在此处没有立即产生收益但在存在后续负数例如[2, 3, -2, 4, -1]的场景中curMin × (-1) 12会成为新的最大值。这就是跟踪最小值的意义所在。方法四前缀与后缀乘积思路核心洞察是最大乘积子数组必然以某段的前缀乘积或后缀乘积的形式出现。原因如下若子数组含偶数个负数整段乘积为正直接取全段即可若含奇数个负数去掉到第一个负数的前缀或最后一个负数之后的后缀即可得到最大乘积零会彻底切断子数组乘积必须在零之后重新开始。因此只需从左到右扫描一次前缀乘积、从右到左扫描一次后缀乘积就隐式覆盖了所有合法子数组无需显式统计负数。前缀或 1的小技巧用于在遇到 0 之后重置乘积。算法步骤初始化res nums[0]prefix 0suffix 0对i从0到n - 1prefix nums[i] * (prefix if prefix ! 0 else 1)suffix nums[n - 1 - i] * (suffix if suffix ! 0 else 1)res max(res, prefix, suffix)返回res。实现细节上javascript/0152-maximum-product-subarray.js 的前缀/后缀变体还在返回前做了res -0 ? 0 : res的归一化避免出现-0这一 JavaScript 特有的坑。复杂度时间复杂度$O(n)$空间复杂度$O(1)$同样满足提示文档的复杂度目标且代码最简洁是面试中值得掌握的第二个线性解法。常见陷阱Common Pitfalls题解文档 articles/maximum-product-subarray.md 末尾总结了三个高频错误这里逐一展开陷阱一忽略负数相乘变正与最大子数组和不同一个非常小的负数乘积在乘上另一个负数后可能成为最大值。只跟踪当前最大值是不够的必须同时跟踪curMax与curMin因为curMin × 负数可能产生新的最大值。陷阱二忘记处理零数组中的零会把乘积重置为 0等价于把数组切分成独立的段。遇到零后子数组必须重新开始若沿用旧的乘积继续累乘会错误地把 0 之后的结果污染。陷阱三更新前未保存旧的最大值计算新的curMin时依赖旧的curMax。如果先更新curMax再用新值计算curMin会得到错误结果。正确做法是先用临时变量保存curMax * num再依次更新两个状态——这也是所有仓库实现中tmp/temp变量的由来可对照 python/0152-maximum-product-subarray.py 第 9 行与 cpp/0152-maximum-product-subarray.cpp 第 11 行。四种方法对比与总结方法时间复杂度空间复杂度核心思想适用场景暴力枚举$O(n^2)$$O(1)$枚举全部子数组小规模数据、验证正确性滑动窗口按零切分$O(n)$$O(n)$零切段 负数计数控制窗口理解零与负数交互的中间方案Kadane 双状态 DP$O(n)$$O(1)$curMax/curMin同步维护最优解推荐掌握前缀/后缀乘积$O(n)$$O(1)$双向累积乘积隐式覆盖子数组代码最简的线性方案针对本仓库 hints/maximum-product-subarray.md 的完整提示链路可以概括为从 O(n²) 的暴力法出发提示 1意识到引入新元素时只需维护最小、最大两个乘积值提示 2最终收敛到同时跟踪curMax/curMin并在三者新开子数组、乘以旧最大、乘以旧最小中取极值的 Kadane 变体提示 3配合全局res记录答案即可达成 O(n) 时间、O(1) 空间的最优解。多语言完整实现可继续查阅仓库python、cpp、java、go、javascript、rust、kotlin、swift等目录下对应的0152-maximum-product-subarray文件。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 152 最大乘积子数组（Maximum Product Subarray）：Kadane 双状态动态规划题解
LeetCode 152 最大乘积子数组Maximum Product SubarrayKadane 双状态动态规划题解【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 LeetCode 152「最大乘积子数组」Maximum Product Subarray展开以本仓库 hints/maximum-product-subarray.md 给出的复杂度目标与解题提示为主线结合 articles/maximum-product-subarray.md 的完整题解与各语言源码实现讲解从暴力枚举到 Kadane 风格双状态动态规划的完整推导路径。读完本文你将掌握为何求乘积的最大子数组不能照搬最大子数组和的单状态 DP、如何用curMax与curMin两个状态解决负数翻转问题以及零值拆分、前缀/后缀扫描等工程化技巧。问题定义与复杂度目标给定一个整数数组nums要求找出数组中乘积最大的连续子数组并返回该乘积。题目保证结果落在 32 位整数范围内。仓库提示文档 hints/maximum-product-subarray.md 首先给出了明确的目标约束时间复杂度O(n)其中n为输入数组长度空间复杂度O(1)。也就是说最优解必须是一次线性扫描、只使用常数级额外空间的算法。以此为标尺我们可以依次评估暴力法、滑动窗口、Kadane 双状态 DP 与前缀/后缀扫描四种方案的取舍。前置知识在动手前建议先掌握以下三点见 articles/maximum-product-subarray.md 的 Prerequisites 部分动态规划 / Kadane 算法理解在单次遍历中跟踪最优子数组值的思路负数乘积的符号翻转负负得正导致只跟踪最大值不够必须同时跟踪最小值前缀/后缀累积乘积利用双向累积乘积定位最优子数组。方法一暴力枚举Brute Force思路子数组的乘积会因为两个因素发生剧烈变化负数会把当前最大值翻转为最小值反之亦然零会把乘积重置为 0。暴力法的策略是显式枚举所有可能的连续子数组固定起始下标i不断向右累乘记录过程中出现过的最大乘积。由于每个子数组都被逐一计算结果必然正确但代价高昂。算法步骤用res记录答案初始化为nums[0]对每个起始下标i令cur nums[i]并更新res对每个j i执行cur * nums[j]并更新res返回res。Python 实现来自 articles/maximum-product-subarray.mdclass Solution: def maxProduct(self, nums: List[int]) - int: res nums[0] for i in range(len(nums)): cur nums[i] res max(res, cur) for j in range(i 1, len(nums)): cur * nums[j] res max(res, cur) return res本仓库 javascript/0152-maximum-product-subarray.js 中也保留了等价的暴力实现linearSearchgetMax双层循环并在注释中标注其复杂度为Time O(N^2) | Space O(1)。复杂度时间复杂度$O(n ^ 2)$空间复杂度$O(1)$这正是提示 1 指出的方向暴力法可以正确求解但达不到 O(n) 的目标需要转向动态规划思路。方法二按零切分的滑动窗口思路最大乘积子数组问题的难点在于负数翻转符号零打断乘积。任何跨越零的子数组乘积都会被归零因此可以把数组按零切分成若干个不含零的段。在每段内部若负数个数为偶数整段乘积为正通常就是最优解若负数个数为奇数则必须丢弃从段首到第一个负数的前缀或从最后一个负数到段尾的后缀使剩余部分包含偶数个负数。这种滑动窗口思路维护一个负数个数合法偶数的窗口超出时从左端收缩。算法步骤以数组中的最大元素初始化res覆盖全为负数或全为零的情况按零切分nums为若干无零段对每段统计负数个数negs确定窗口应保留的负数个数need负数为偶数时need negs为奇数时need negs - 1用双指针j..i维护运行乘积i右扩累乘窗口内负数超过need时移动j并除掉左侧元素窗口合法时用当前prod更新res返回res。复杂度时间复杂度$O(n)$空间复杂度$O(n)$需要额外存储切分后的段该方案虽然达到线性时间但空间不符合 O(1) 要求且实现中通过除法回退乘积在含零场景下需要格外小心因此实际更推荐下面的 Kadane 双状态 DP。方法三Kadane 算法双状态动态规划——最优解思路经典的最大子数组和问题只需跟踪一个状态当前最大和。但乘积问题不行负 × 负 正一个很小的负数在乘上另一个负数后可能一跃成为最大值因此每个下标处必须同时跟踪两个值curMax以当前下标结尾的最大乘积curMin以当前下标结尾的最小乘积。curMin的价值在于当当前数字为负时num * curMin最小负数乘负数可能产生新的最大值。而零值天然被处理——因为候选值中包含num本身遇到零即可重新开始。这正是提示 2 与提示 3 的核心在引入新元素时只需维护最小、最大两个乘积值分别考虑新开子数组乘以之前的最大乘积乘以之前的最小乘积三种情况全局最大乘积单独跟踪。提示 3 明确指出这就是 Kadane 算法的变体。算法步骤初始化res nums[0]curMax 1curMin 1遍历每个num先用临时变量tmp保存curMax * num因为curMax即将被更新curMax max(num * curMax, num * curMin, num)curMin min(tmp, num * curMin, num)res max(res, curMax)返回res。多语言实现仓库各语言实现完全一致可直接对照学习。Pythonpython/0152-maximum-product-subarray.pyclass Solution: def maxProduct(self, nums: List[int]) - int: # O(n)/O(1) : Time/Memory res nums[0] curMin, curMax 1, 1 for n in nums: tmp curMax * n curMax max(n * curMax, n * curMin, n) curMin min(tmp, n * curMin, n) res max(res, curMax) return resCcpp/0152-maximum-product-subarray.cppclass Solution { public: int maxProduct(vectorint nums) { int res nums[0]; int curMin 1, curMax 1; for(int i 0; i nums.size(); i) { int n nums[i]; int tmp curMax * n; curMax max(max(n * curMax, n * curMin), n); curMin min(min(tmp, n * curMin), n); res max(res, curMax); } return res; } };Javajava/0152-maximum-product-subarray.java额外处理了单元素数组的边界情况class Solution { public int maxProduct(int[] nums) { if (nums.length 1) return nums[0]; int res nums[0]; int max 1; int min 1; for (int n : nums) { int tmp max * n; max Math.max(n, Math.max(tmp, min * n)); min Math.min(n, Math.min(tmp, min * n)); res Math.max(res, max); } return res; } }Gogo/0152-maximum-product-subarray.go需要注意 Go 标准库没有整数max/min文件中自行实现了辅助函数func maxProduct(nums []int) int { res, curMin, curMax : nums[0], 1, 1 for i : 0; i len(nums); i { temp : curMax * nums[i] curMax max(max(nums[i] * curMax, nums[i] * curMin), nums[i]) curMin min(min(temp, nums[i] * curMin), nums[i]) res max(res, curMax) } return res }Rustrust/0152-maximum-product-subarray.rs用Vec的iter().max()/iter().min()表达三者取极值并用nums.iter().max()初始化res与 Java 的单元素特判殊途同归impl Solution { pub fn max_product(nums: Veci32) - i32 { let (mut res, mut big, mut small) (*nums.iter().max().unwrap(), 1, 1); for n in nums { let tmp big; big vec![n, big * n, small * n].into_iter().max().unwrap(); small vec![n, tmp * n, small * n].into_iter().min().unwrap(); res res.max(big); } res } }复杂度时间复杂度$O(n)$空间复杂度$O(1)$完全满足提示文档设定的目标是本题的标准最优解。一次遍历正确性示例以nums [2, 3, -2, 4]为例下标numcurMax 计算curMin 计算res02max(2×1, 2×1, 2) 2min(2, 2, 2) 2213max(6, 6, 3) 6min(6, 6, 3) 362-2max(-12, -6, -2) -2min(-12, -6, -2) -12634max(-8, -48, 4) 4min(-8, -48, 4) -486注意下标 2 处curMin -12被保存下来它正是以-2结尾的最小乘积2 × 3 × -2虽然它在此处没有立即产生收益但在存在后续负数例如[2, 3, -2, 4, -1]的场景中curMin × (-1) 12会成为新的最大值。这就是跟踪最小值的意义所在。方法四前缀与后缀乘积思路核心洞察是最大乘积子数组必然以某段的前缀乘积或后缀乘积的形式出现。原因如下若子数组含偶数个负数整段乘积为正直接取全段即可若含奇数个负数去掉到第一个负数的前缀或最后一个负数之后的后缀即可得到最大乘积零会彻底切断子数组乘积必须在零之后重新开始。因此只需从左到右扫描一次前缀乘积、从右到左扫描一次后缀乘积就隐式覆盖了所有合法子数组无需显式统计负数。前缀或 1的小技巧用于在遇到 0 之后重置乘积。算法步骤初始化res nums[0]prefix 0suffix 0对i从0到n - 1prefix nums[i] * (prefix if prefix ! 0 else 1)suffix nums[n - 1 - i] * (suffix if suffix ! 0 else 1)res max(res, prefix, suffix)返回res。实现细节上javascript/0152-maximum-product-subarray.js 的前缀/后缀变体还在返回前做了res -0 ? 0 : res的归一化避免出现-0这一 JavaScript 特有的坑。复杂度时间复杂度$O(n)$空间复杂度$O(1)$同样满足提示文档的复杂度目标且代码最简洁是面试中值得掌握的第二个线性解法。常见陷阱Common Pitfalls题解文档 articles/maximum-product-subarray.md 末尾总结了三个高频错误这里逐一展开陷阱一忽略负数相乘变正与最大子数组和不同一个非常小的负数乘积在乘上另一个负数后可能成为最大值。只跟踪当前最大值是不够的必须同时跟踪curMax与curMin因为curMin × 负数可能产生新的最大值。陷阱二忘记处理零数组中的零会把乘积重置为 0等价于把数组切分成独立的段。遇到零后子数组必须重新开始若沿用旧的乘积继续累乘会错误地把 0 之后的结果污染。陷阱三更新前未保存旧的最大值计算新的curMin时依赖旧的curMax。如果先更新curMax再用新值计算curMin会得到错误结果。正确做法是先用临时变量保存curMax * num再依次更新两个状态——这也是所有仓库实现中tmp/temp变量的由来可对照 python/0152-maximum-product-subarray.py 第 9 行与 cpp/0152-maximum-product-subarray.cpp 第 11 行。四种方法对比与总结方法时间复杂度空间复杂度核心思想适用场景暴力枚举$O(n^2)$$O(1)$枚举全部子数组小规模数据、验证正确性滑动窗口按零切分$O(n)$$O(n)$零切段 负数计数控制窗口理解零与负数交互的中间方案Kadane 双状态 DP$O(n)$$O(1)$curMax/curMin同步维护最优解推荐掌握前缀/后缀乘积$O(n)$$O(1)$双向累积乘积隐式覆盖子数组代码最简的线性方案针对本仓库 hints/maximum-product-subarray.md 的完整提示链路可以概括为从 O(n²) 的暴力法出发提示 1意识到引入新元素时只需维护最小、最大两个乘积值提示 2最终收敛到同时跟踪curMax/curMin并在三者新开子数组、乘以旧最大、乘以旧最小中取极值的 Kadane 变体提示 3配合全局res记录答案即可达成 O(n) 时间、O(1) 空间的最优解。多语言完整实现可继续查阅仓库python、cpp、java、go、javascript、rust、kotlin、swift等目录下对应的0152-maximum-product-subarray文件。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考