152. 乘积最大子数组 (Medium)
专题归类： 10-动态规划 LeetCode 链接： https://leetcode.cn/problems/maximum-product-subarray/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1：
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2：
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2，因为 [-2,-1] 不是子数组。
提示：
- 1 <= nums.length <= 2 * 10
- -10 <= nums[i] <= 10
- nums 的任何子数组的乘积都在 32 位整数范围内
题目详细分析
- 数据范围：长度最大 2*10^4，O(n) 算法是必须的。
- 核心约束：子数组是连续的（与子序列不同）。元素值范围 [-10, 10]，有正数、负数和零。
- 边界条件：单元素数组直接返回该元素；零会把乘积断成两段。
- 隐藏条件：负数乘负数会变正数，所以不能只记录最大值，必须同时记录最小值（最负的数），因为最小负数乘负数可能变成最大正数。
小白版直白理解
找一段连续的数字让它们的乘积最大。和”最大子数组和”不同，乘法有负负得正的问题。想象你在滚雪球：
- 如果遇到正数，雪球越滚越大（max 变大）
- 如果遇到负数，大雪球变小，小雪球反而变大（因为负负得正）
- 如果遇到 0，雪球就化掉了，得从头滚
所以你得同时盯着”最大雪球”和”最小雪球”，因为最小的那个碰到负数可能会翻身。
解题思路
思路一：动态规划（维护最大最小值，推荐）
核心洞察：由于负数的存在，当前最大乘积可能来自之前的最大正数乘正数，也可能来自之前的最小负数乘负数。因此同时维护当前最大 max_prod 和当前最小 min_prod。
DP 五步法：
- dp 定义：
max_prod[i]表示以 i 结尾的子数组最大乘积，min_prod[i]表示最小乘积 - 递推公式：
max_prod[i] = max(nums[i], max_prod[i-1] * nums[i], min_prod[i-1] * nums[i])min_prod[i] = min(nums[i], max_prod[i-1] * nums[i], min_prod[i-1] * nums[i])
- 初始化：
max_prod[0] = min_prod[0] = nums[0] - 遍历顺序：从左到右
- 举例验证：nums=[2,3,-2,4] → i=0: max=2,min=2,res=2; i=1: max=6,min=3,res=6; i=2: max=max(-2,6*(-2),3*(-2))=-2, min=-12, res=6; i=3: max=max(4,-24,-124)=4, min=-48, res=6 ✓
def maxProduct(nums):
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
# 如果遇到负数，最大和最小互换（因为乘以负数后大小关系翻转）
if num < 0:
max_prod, min_prod = min_prod, max_prod
# 更新当前最大/最小乘积
max_prod = max(num, max_prod * num)
min_prod = min(num, min_prod * num)
# 更新全局最大
result = max(result, max_prod)
return result思路二：无交换写法（不依赖 if-else）
对三种情况统一求最大/最小，避免手动交换。
def maxProduct(nums):
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
candidates = (max_prod * num, min_prod * num, num)
max_prod = max(candidates)
min_prod = min(candidates)
result = max(result, max_prod)
return result思路三：前缀积 + 后缀积
分别从前往后和从后往前计算累计乘积，遇到 0 重置为 1，取所有值的最大值。
def maxProduct(nums):
n = len(nums)
prefix = suffix = 1
result = -float('inf')
for i in range(n):
prefix *= nums[i]
suffix *= nums[n - 1 - i]
result = max(result, prefix, suffix)
if prefix == 0:
prefix = 1
if suffix == 0:
suffix = 1
return result易错点
- 负数处理：遇到负数时，最大和最小要互换（因为负数使得大的变小、小的变大）。
- 乘以 0：遇到 0 时，乘积变为 0，后续需要重新累积。前缀积解法中要重置为 1。
- 单元素数组：初始值设为
nums[0]，遍历从 index=1 开始。 - 结果溢出不考虑：题目保证结果在 32 位整型范围内。
框架提炼
Kadane 算法变体（同时维护最大/最小值）模板：
def kadane_variant(nums):
cur_max = cur_min = result = nums[0]
for num in nums[1:]:
# 遇到负数交换最大最小值
if num < 0:
cur_max, cur_min = cur_min, cur_max
cur_max = max(num, cur_max * num)
cur_min = min(num, cur_min * num)
result = max(result, cur_max)
return result这种”双变量”维护模式适用于需要同时追踪正负两个极值的场景。
关联题目
- 53-最大子数组和 — Kadane 算法的加法版（无需维护最小值）
- 300-最长递增子序列 — 子数组 vs 子序列 DP 的区别
- 238-除自身以外数组的乘积 — 前缀积/后缀积的另一种应用