乘积最大子数组（Maximum Product Subarray）

题目描述
给定一个整数数组 nums，请找出数组中乘积最大的连续子数组，并返回该乘积。子数组是数组中连续的一个非空序列。乘积可以是负数、零或正数，但题目要求返回最大乘积。
例如：
输入：[2,3,-2,4]
输出：6
解释：子数组 [2,3] 的乘积为 6，是最大的连续子数组乘积。

解题过程
这是一个经典的线性动态规划问题。难点在于乘积有正负之分，负数乘以负数会变成正数，所以不能只记录以每个位置结尾的最大乘积，还需要记录最小乘积（因为最小负数乘以负数可能变成最大正数）。

步骤1：定义状态
定义两个一维数组（或变量）：

• maxProd[i]：表示以第 i 个元素结尾的连续子数组的最大乘积。
• minProd[i]：表示以第 i 个元素结尾的连续子数组的最小乘积（可能是负数）。

步骤2：状态转移方程
对于每个位置 i，考虑前一个状态（i-1）和当前值 nums[i]：

1. 如果 nums[i] 是正数，那么：
   • 最大乘积可能是前一个最大乘积乘以 nums[i]（正数），或者就是 nums[i] 自己（比如前一个乘积是负数，不如从当前重新开始）。
   • 最小乘积类似，可能是前一个最小乘积乘以 nums[i]（正数），或者 nums[i] 自己。
2. 如果 nums[i] 是负数，那么：
   • 最大乘积可能是前一个最小乘积（负数）乘以 nums[i]（负数变正数），或者 nums[i] 自己。
   • 最小乘积可能是前一个最大乘积（正数）乘以 nums[i]（正数变负数），或者 nums[i] 自己。
3. 如果 nums[i] 是零，那么最大乘积和最小乘积都为零（因为任何数乘以零都是零）。

综合起来，统一的状态转移方程为：

maxProd[i] = max(nums[i], maxProd[i-1] * nums[i], minProd[i-1] * nums[i])
minProd[i] = min(nums[i], maxProd[i-1] * nums[i], minProd[i-1] * nums[i])

然后全局最大乘积就是所有 maxProd[i] 中的最大值。

步骤3：初始化
对于 i=0，只有 nums[0] 一个元素，所以：

maxProd[0] = nums[0]
minProd[0] = nums[0]

全局最大值初始化为 nums[0]。

步骤4：计算顺序
从左到右遍历数组，用滚动变量（而非数组）节省空间：用 curMax 和 curMin 代替 maxProd[i] 和 minProd[i]，每次更新前用临时变量保存旧的 curMax 和 curMin，避免新计算的 curMax 影响 curMin 的计算。

步骤5：举例说明
以 nums = [2,3,-2,4] 为例：

• i=0: curMax=2, curMin=2, ans=2
• i=1: 旧 curMax=2, 旧 curMin=2, 新 curMax = max(3, 23=6, 23=6) = 6, 新 curMin = min(3, 23=6, 23=6) = 3, ans=max(2,6)=6
• i=2: 旧 curMax=6, 旧 curMin=3, 新 curMax = max(-2, 6*(-2)=-12, 3*(-2)=-6) = -2, 新 curMin = min(-2, 6*(-2)=-12, 3*(-2)=-6) = -12, ans=max(6,-2)=6
• i=3: 旧 curMax=-2, 旧 curMin=-12, 新 curMax = max(4, -24=-8, -124=-48) = 4, 新 curMin = min(4, -24=-8, -124=-48) = -48, ans=max(6,4)=6
  最终 ans=6。

步骤6：时间复杂度与空间复杂度
时间复杂度 O(n)，空间复杂度 O(1)（使用滚动变量）。

步骤7：边界情况

• 数组长度为1：直接返回该元素。
• 包含0：0 会中断乘积链，但状态转移中 max(0, ...) 会自然处理，从下一个非零元素重新开始计算乘积。
• 全是负数：比如 [-2,-3,-1]，最大乘积可能是正数（-2*-3=6），最小乘积可能是负数（-3），需正确记录。

步骤8：代码框架（Python）

def maxProduct(nums):
    if not nums:
        return 0
    cur_max = cur_min = ans = nums[0]
    for i in range(1, len(nums)):
        temp_max = cur_max
        cur_max = max(nums[i], cur_max * nums[i], cur_min * nums[i])
        cur_min = min(nums[i], temp_max * nums[i], cur_min * nums[i])
        ans = max(ans, cur_max)
    return ans

这样，我们就循序渐进地解决了乘积最大子数组问题。关键在于同时维护最大和最小乘积，以处理正负号变化带来的影响。