我来给你讲解 LeetCode 第 152 题：乘积最大子数组（Maximum Product Subarray）。

题目描述

给你一个整数数组 nums，请找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例保证结果是一个 32 位整数。

示例 1：

输入：nums = [2,3,-2,4]
输出：6
解释：子数组 [2,3] 有最大乘积 6。

示例 2：

输入：nums = [-2,0,-1]
输出：0
解释：结果不能为 2，因为 [-2,-1] 不是子数组。

解题思路详解

第一步：理解问题的特殊性

这个问题与"最大子数组和"（第53题）看起来很相似，但有一个关键区别：乘法具有符号效应。

• 在加法中，负数只会让和变小
• 在乘法中，负数可能让乘积从最小变成最大（当再乘以一个负数时）

关键观察：我们需要同时跟踪当前的最大乘积和最小乘积。

第二步：动态规划状态定义

我们定义两个状态数组：

• maxDP[i]：以第 i 个元素结尾的子数组的最大乘积
• minDP[i]：以第 i 个元素结尾的子数组的最小乘积

状态转移方程：

maxDP[i] = max(nums[i], maxDP[i-1] * nums[i], minDP[i-1] * nums[i])
minDP[i] = min(nums[i], maxDP[i-1] * nums[i], minDP[i-1] * nums[i])

第三步：为什么需要同时跟踪最大和最小值？

考虑三种情况：

1. 当前数是正数：我们希望乘以尽可能大的数
2. 当前数是负数：我们希望乘以尽可能小的数（负负得正）
3. 当前数是0：最大和最小都重置为0

示例分析：nums = [2, 3, -2, 4]

全局最大值在遍历过程中出现：6

第四步：空间优化

由于每个状态只依赖于前一个状态，我们可以用变量代替数组：

def maxProduct(nums):
    if not nums:
        return 
    
    max_so_far = min_so_far = result = nums[0]
    
    for i in range(1, len(nums)):
        curr = nums[i]
        
        # 临时变量保存，因为max_so_far会被更新
        temp_max = max(curr, max_so_far * curr, min_so_far * curr)
        min_so_far = min(curr, max_so_far * curr, min_so_far * curr)
        max_so_far = temp_max
        
        result = max(result, max_so_far)
    
    return result

第五步：详细步骤演示

以 nums = [2, 3, -2, 4] 为例：

1. 初始化：max_so_far = 2, min_so_far = 2, result = 2
2. i=1 (num=3)：
   • 可能值：3, 2×3=6, 2×3=6 → max=6, min=3
   • result = max(2,6)=6
3. i=2 (num=-2)：
   • 可能值：-2, 6×-2=-12, 3×-2=-6 → max=-2, min=-12
   • result = max(6,-2)=6
4. i=3 (num=4)：
   • 可能值：4, -2×4=-8, -12×4=-48 → max=4, min=-48
   • result = max(6,4)=6

最终结果：6

第六步：边界情况处理

• 空数组：根据题意保证非空
• 单个元素：[5] → 返回5
• 包含0：[2,0,3] → 正确处理重置
• 全负数：[-2,-3,-1] → 最大乘积是(-2)×(-3)=6

第七步：算法复杂度

• 时间复杂度：O(n)，只需遍历一次数组
• 空间复杂度：O(1)，只用了常数个变量

这个算法的核心思想是通过同时维护最大和最小乘积，来应对乘法中负数带来的符号变化问题。