#152
中等
低频
动态规划乘积最大子数组
这是一道围绕数组展开的高频练习。建议先掌握「动态规划」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
题目分析
给你一个整数数组，要求找出其中乘积最大的连续子数组，并返回这个最大乘积。
注意这里强调的是连续子数组，不能跳着选。
一句话概括：
因为负数会让最小值翻成最大值，所以当前位置必须同时维护最大乘积和最小乘积。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：同时维护以当前位置结尾的最大乘积和最小乘积，因为负数会让两者互换角色。
推荐代码
推荐解法：动态规划
时间复杂度： O(n)
空间复杂度： O(1)
核心思路： 同时维护以当前位置结尾的最大乘积和最小乘积，因为负数会让两者互换角色。
class Solution {
public int maxProduct(int[] nums) {
// 初始化全局最大值、当前最大值和当前最小值
int max = Integer.MIN_VALUE, imax = 1, imin = 1;
for (int i = 0; i < nums.length; i++) {
// 当遇到负数时，交换imax和imin
if (nums[i] < 0) {
int tmp = imax;
imax = imin;
imin = tmp;
}
// 更新imax和imin
imax = Math.max(imax * nums[i], nums[i]);
imin = Math.min(imin * nums[i], nums[i]);
// 更新全局最大值
max = Math.max(max, imax);
}
return max;
}
}
结构化讲解
面试时怎么讲
开场思路
这题我会用状态压缩 DP，同时维护当前位置结尾的最大积和最小积。
核心过程
- 初始化当前最大积、最小积和全局答案为首元素。
- 遍历到新元素时，如果它是负数，就先交换当前最大和最小积。
- 然后分别更新以当前位置结尾的最大积和最小积。
- 最后用当前最大积刷新全局答案。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(1)。
面试补一句：这题最关键的一句解释是：负数会让最大积和最小积互换角色。
核心思路
最大乘积子数组和最大和子数组不同，关键在于负数。一个很小的负积乘上负数后可能瞬间变成最大正积，所以最大值和最小值都必须保留。
步骤讲解
1
同时维护最大积和最小积
遍历到每个位置时，记录以它结尾的最大乘积 maxProd 和最小乘积 minProd。
为什么这样做：负数会把最大值和最小值的角色翻转，不能只保留一个状态。
对应代码提示：int maxProd = nums[0], minProd = nums[0];
2
当前数为负时先交换两者
若当前元素是负数，先交换 maxProd 和 minProd，再更新。
为什么这样做：负数乘法会把原来的最小负积变成潜在最大正积。
对应代码提示：if (num < 0) { int temp = maxProd; maxProd = minProd; minProd = temp; }
3
用当前位置刷新状态和全局答案
更新当前结尾的最大/最小乘积后，再用最大乘积刷新全局答案。
为什么这样做：题目要的是任意位置结尾的最大乘积子数组。
对应代码提示：maxProd = Math.max(num, maxProd * num); answer = Math.max(answer, maxProd);
易错点
只维护最大乘积
这样会漏掉“负负得正”带来的反转机会。
正确理解：必须同时维护最大乘积和最小乘积。
遇到负数没先交换状态
更新顺序错了会把旧状态覆盖掉，转移不成立。
正确理解：当前数为负时，先交换再更新。
把它套成最大子数组和模板
乘法受符号影响，和的 Kadane 模板不能直接照搬。
正确理解：重新从“负数翻转最大最小”的角度定义状态。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(1)
比其他方案更好在哪里：比暴力枚举所有子数组高效得多，也比只记最大值的错误思路更完整。
适用判断：序列乘积题里只要出现负数，优先考虑同时维护最大/最小状态。
额外提醒
- 最小乘积不是副产品，而是得到最大乘积的关键跳板。
动画演示
如果你还没完全看懂，可以展开动画演示。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入数组值（用逗号分隔），然后点击开始
动画结果
点击开始按钮查看动画结果
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。