LeetCode 152. 乘积最大子数组
目录
题目描述
题意分析
给定整数数组
nums，找出其中乘积最大的非空连续子数组，返回该乘积。子数组必须连续，且至少包含一个元素。如果把「乘积」换成「和」，只维护一个「以当前位置结尾的最大值」就够了。但乘法有两个特殊之处，让这条路走不通：一是负负得正——当前一个很小的负数乘积，再乘一个负数可能瞬间翻身成最大值，只盯着「最大」会把这种翻盘机会提前丢掉；二是 0 会截断——任何乘积碰到 0 都归零，0 之后必须从头再来。
数据范围上，题目保证任何前缀或子数组的乘积都在 32 位整数范围内，所以不需要考虑溢出。
边界方面：数组非空但可能只有一个元素（且可能是负数或 0），答案至少是数组中的某个单元素，因此答案的初始值必须取自数组本身，不能凭空写 0 或 1。
解法：同时维护最大和最小乘积
核心思路
问题关键：乘法遇到负数会让大小关系反转。只记录「以当前位置结尾的最大乘积」会丢掉一个很小的负数，而它可能在后面乘负数后变成最大值。
为什么选动态规划：每个连续子数组都可以看成「以前一位结尾的子数组再接上当前数」，因此只需保留上一位的结果，不必枚举左右端点。
状态与不变量：处理完
nums[i]后，maxProd、minProd分别是所有以i结尾的非空子数组中的最大、最小乘积。加入num时只有三种候选：从num重新开始，或把num接到旧的最大、最小乘积后面，因此转移为：
newMax = max(num, oldMax * num, oldMin * num)newMin = min(num, oldMax * num, oldMin * num)三种可能被完整覆盖，所以状态始终成立；答案取所有结尾位置的
maxProd最大值。候选中保留num，也让 0 后的状态自然重新开始，无需额外分段。
解题步骤
- 用
nums[0]初始化maxProd、minProd和ans，保证单元素、全负数组也正确。- 从下标 1 开始遍历，先保存
oldMax、oldMin，避免更新一个状态后污染另一个状态。- 用当前数与两个旧状态计算新的最大、最小乘积；裸的
num表示从当前位置重新开始。- 用新的
maxProd更新全局答案。遍历结束后返回ans。例如处理
[-2, 3, -4]时，到3为止最小乘积是-6；再遇到-4，它翻转成最大候选24。这正是必须保留minProd的原因。
代码实现
class Solution {
public int maxProduct(int[] nums) {
int maxProd = nums[0];
int minProd = nums[0];
int ans = nums[0];
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
int oldMax = maxProd;
int oldMin = minProd;
// 负数会让最大乘积和最小乘积角色互换。
maxProd = Math.max(num, Math.max(oldMax * num, oldMin * num));
minProd = Math.min(num, Math.min(oldMax * num, oldMin * num));
ans = Math.max(ans, maxProd);
}
return ans;
}
}
func maxProduct(nums []int) int {
maxProd := nums[0]
minProd := nums[0]
ans := nums[0]
for i := 1; i < len(nums); i++ {
num := nums[i]
oldMax := maxProd
oldMin := minProd
// 当前数为负时，旧最小值可能变成新的最大值。
maxProd = maxInt(num, maxInt(oldMax*num, oldMin*num))
minProd = minInt(num, minInt(oldMax*num, oldMin*num))
ans = maxInt(ans, maxProd)
}
return ans
}
func maxInt(a int, b int) int {
if a > b {
return a
}
return b
}
func minInt(a int, b int) int {
if a < b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(n)$，数组只遍历一次。
- 空间复杂度：$O(1)$，只维护两个滚动状态和答案。
关键点总结
- 面试时先指出「负数会交换最大与最小」，再自然推出双状态，这是本题主线。
- 状态限定为「以当前位置结尾」，才能从前一位做常数时间转移。
- 裸的
num同时承担重新起点和处理 0 的作用。- 两个新状态都依赖上一轮值，更新前必须保留旧状态。
易错点总结
- 只维护最大乘积会漏掉负负得正：
[-2,3,-4]的正确答案是24，不是3。ans不能初始化为0；单元素[-2]的答案是-2。- 转移不能漏掉裸的
num，否则[0,2]无法在 0 后重新开始。- 不能直接用更新后的
maxProd计算minProd，两者都必须基于上一轮状态。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 53. 最大子数组和 | 中等 | 加法版本，单一最大状态即可，本题的前置题 |
| 1567. 乘积为正数的最长子数组长度 | 中等 | 同样双状态，但维护的是正/负乘积的长度而非值 |
| 1186. 删除一次得到子数组最大和 | 中等 | 加法上叠加「删或不删」维度的双状态 DP |