LeetCode 152中等动态规划 · 最大最小
乘积最大子数组 图解题解
这道题到底在问什么
找乘积最大的连续子数组。
- nums
- [2,3,-2,4]
- 输出
- 6
最优解：一步一步想明白
- 3关键不是背模板，而是看懂为什么这题适合动态规划 · 最大最小。
- 4乘积里负数会翻身:最小(负)×负 → 变最大。所以同时维护 imax(以当前结尾的最大积)和 imin(最小积)。起点 2:imax=imin=ans=2。
- 5×3(正数):imax=max(3, 2×3)=6,imin=min(3, 2×3)=3。ans 更新到 6。
- 6关键帧:到 -2(负数)→ 先交换 imax 与 imin(因为最小×负 才可能变最大)。交换后 imax=max(-2, 3×-2)=-2,imin=min(-2, 6×-2)=-12。ans 仍 6。
- 7×4(正数):imax=max(4, -2×4)=4,imin=min(4, -12×4)=-48。ans 仍 6。
- 8扫完,答案 ans=6,来自子数组 [2,3]。负数被 imin 接住,正数让 imax 增长。
- 11把这句话记住，下次遇到同类题，就能更快选出方向。
- 16把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
⚠️ 容易写错的地方
✗ 错：只维护最大值
✓ 对：同时维护最大和最小
负数乘最小可能变最大
✗ 错：遇负数不交换 imax/imin
✓ 对：负数前先 swap，再各自乘
负数让最小变最大、最大变最小，不交换会算错。
✗ 错：imax/imin 初值设 0 或 1
✓ 对：初值都设 nums[0]
子数组非空；设 0/1 会污染第一个元素的积。
完整代码（Python / C++ / Java）
Python
class Solution:
def maxProduct(self, nums):
imax = imin = ans = nums[0]
for x in nums[1:]:
if x < 0:
imax, imin = imin, imax
imax = max(x, imax * x)
imin = min(x, imin * x)
ans = max(ans, imax)
return ansC++
class Solution {
public:
int maxProduct(vector<int>& nums) {
int imax = nums[0], imin = nums[0], ans = nums[0];
for (int i = 1; i < (int)nums.size(); i++) {
int x = nums[i];
if (x < 0) swap(imax, imin);
imax = max(x, imax * x);
imin = min(x, imin * x);
ans = max(ans, imax);
}
return ans;
}
};Java
class Solution {
public int maxProduct(int[] nums) {
int imax = nums[0], imin = nums[0], ans = nums[0];
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
if (x < 0) { int tmp = imax; imax = imin; imin = tmp; }
imax = Math.max(x, imax * x);
imin = Math.min(x, imin * x);
ans = Math.max(ans, imax);
}
return ans;
}
}套路模板 · 动态规划 · 最大最小
# 动态规划 · 最大最小 通用检查表
# 1. 定义状态/指针/容器
# 2. 每轮只做一个清晰动作
# 3. 更新答案并处理边界class Solution {
public:
int maxProduct(vector<int>& nums) {
int imax = nums[0], imin = nums[0], ans = nums[0];
for (int i = 1; i < (int)nums.size(); i++) {
int x = nums[i];
if (x < 0) swap(imax, imin);
imax = max(x, imax * x);
imin = min(x, imin * x);
ans = max(ans, imax);
}
return ans;
}
};class Solution {
public int maxProduct(int[] nums) {
int imax = nums[0], imin = nums[0], ans = nums[0];
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
if (x < 0) { int tmp = imax; imax = imin; imin = tmp; }
imax = Math.max(x, imax * x);
imin = Math.min(x, imin * x);
ans = Math.max(ans, imax);
}
return ans;
}
}复杂度
时间复杂度
O(n)
每个核心状态按算法要求处理固定次数
空间复杂度
O(1)
只保存必要的辅助结构或递归栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 乘积最大子数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么和「最大子数组和 LC53」不同要记两个？+
加法没有负负得正；乘法里负数翻转大小，所以同时跟踪最大积和最小积，负数来时互换。
遇到 0 怎么办？+
0 让乘积归零，相当于从这里切断、重新开始一段。
复杂度？+
O(n) 时间、O(1) 空间。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。