题目描述
LeetCode 152. 乘积最大子数组
给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组的乘积。
注意：子数组必须是连续的。
示例
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组（不连续，中间有0）。
输入: nums = [-2,3,-4]
输出: 24
解释: 子数组 [-2,3,-4] 有最大乘积 24。学习历程（从联想到突破）
第一步：联想最大子数组和
第一反应：这不是经典的 Kadane 算法吗？
dp[i] = max(nums[i], dp[i-1] + nums[i])但是：乘法有个坑——负数 × 负数 = 正数！
反例：nums = [-2, -3]
按照加法逻辑：
-2和-3分开最大但乘法：
-2 × -3 = 6，连续更大！
第二步：关键难点——负数让最大变最小
核心问题：
当前数字是负数时，前面累积的最大值（正数）乘它 → 变成负数（变小）
当前数字是负数时，前面累积的最小值（负数）乘它 → 变成正数（可能变大）
洞察：不能只维护「最大值」，还要维护「最小值」！
第三步：双状态 DP 设计
定义两个状态：
max_dp[i]：以第i个位置结尾的子数组的最大乘积min_dp[i]：以第i个位置结尾的子数组的最小乘积
状态转移（三种选择）：
max_dp[i] = max(nums[i], max_dp[i-1] * nums[i], min_dp[i-1] * nums[i])
min_dp[i] = min(nums[i], max_dp[i-1] * nums[i], min_dp[i-1] * nums[i])为什么三个都要比较？
nums[i]：重开子数组（前面的乘积可能是 0 或负数，不如单独选）max_dp[i-1] * nums[i]：继续前面的最大值min_dp[i-1] * nums[i]：负负得正，可能变成最大
第四步：手动推导验证
以 nums = [-2, 3, -4] 为例：
全局答案 = max(max_dp[0], max_dp[1], max_dp[2]) = 24 ✓
第五步：空间优化——负数交换技巧
观察：dp[i] 只依赖于 dp[i-1]，不需要数组，用变量即可。
** Trick：当 nums[i] < 0 时，先交换** maxProd 和 minProd
if (num < 0) {
// 交换 maxProd 和 minProd
int temp = maxProd;
maxProd = minProd;
minProd = temp;
}
// 这样后面的转移公式可以简化为：
maxProd = max(num, maxProd * num);
minProd = min(num, minProd * num);为什么能交换？
负数会让「最大」变「最小」，「最小」变「最大」
先交换，让
maxProd永远对应「可能最大」的那个避免了
max(a,b,c)和min(a,b,c)的复杂判断
完整代码实现（Java）
public class MaxProductSubarray {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// 初始化：第一个元素
int maxProd = nums[0]; // 以当前位置结尾的最大乘积
int minProd = nums[0]; // 以当前位置结尾的最小乘积
int result = nums[0]; // 全局最大乘积
// 从第二个元素开始遍历
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
// 关键：如果当前数是负数，交换 maxProd 和 minProd
// 因为负数会让最大变最小、最小变最大
if (num < 0) {
int temp = maxProd;
maxProd = minProd;
minProd = temp;
}
// 更新 maxProd：要么重开，要么续上
maxProd = Math.max(num, maxProd * num);
// 更新 minProd：同理
minProd = Math.min(num, minProd * num);
// 更新全局结果
result = Math.max(result, maxProd);
}
return result;
}
// 测试
public static void main(String[] args) {
MaxProductSubarray solution = new MaxProductSubarray();
int[] nums1 = {2, 3, -2, 4};
System.out.println("示例1结果：" + solution.maxProduct(nums1)); // 6
int[] nums2 = {-2, 0, -1};
System.out.println("示例2结果：" + solution.maxProduct(nums2)); // 0
int[] nums3 = {-2, 3, -4};
System.out.println("示例3结果：" + solution.maxProduct(nums3)); // 24
}
}复杂度分析
关键总结
解题模板（双状态 DP）
1. 同时维护 maxProd 和 minProd
2. 遇到负数先交换 maxProd 和 minProd
3. 更新：maxProd = max(num, maxProd * num)
4. 更新：minProd = min(num, minProd * num)
5. 更新全局结果 result = max(result, maxProd)类似题目
易错点复盘
只维护最大值：遇到负数就错了，必须同时维护最小值
忘记交换：负数时如果不交换，会导致状态转移错误
全局结果更新位置：要在循环内每次更新，不是最后才更新
初始值设置：
maxProd和minProd都要初始化为nums[0]忽略单独选的情况：
max(num, maxProd * num)不能漏掉num本身