线性动态规划：乘积最大子数组

题目描述
给定一个整数数组 nums，请找出数组中乘积最大的连续子数组，并返回该子数组的乘积。
示例：
输入：nums = [2, 3, -2, 4]
输出：6
解释：连续子数组 [2, 3] 的乘积为 6，是最大乘积。
注意：子数组要求连续，且乘积可能为正或负，需考虑负数相乘转为正数的情况。

解题过程

步骤 1：分析问题特点

• 若数组元素均为正数，只需逐项相乘并记录最大值。
• 但若存在负数，负数的乘积可能通过再乘一个负数变为正数，因此需同时记录当前最大值和当前最小值。
• 动态规划中，状态设计需包含两个值：以 nums[i] 结尾的子数组的最大乘积 (maxDP[i]) 和最小乘积 (minDP[i])。

步骤 2：定义状态

• 设 maxDP[i] 表示以第 i 个元素结尾的连续子数组的最大乘积。
• 设 minDP[i] 表示以第 i 个元素结尾的连续子数组的最小乘积。
• 最终答案为所有 maxDP[i] 中的最大值。

步骤 3：状态转移方程
对于每个元素 nums[i]：

1. 若 nums[i] ≥ 0：
   • 当前最大值可能是 nums[i] 本身，或 maxDP[i-1] * nums[i]（延续之前正乘积）。
   • 当前最小值可能是 nums[i] 本身，或 minDP[i-1] * nums[i]（延续之前负乘积）。
2. 若 nums[i] < 0：
   • 当前最大值可能是 nums[i] 本身，或 minDP[i-1] * nums[i]（负数乘之前的最小负乘积得正）。
   • 当前最小值可能是 nums[i] 本身，或 maxDP[i-1] * nums[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])

步骤 4：初始化与迭代

• 初始状态：maxDP[0] = minDP[0] = nums[0]。
• 从 i = 1 开始遍历数组，根据转移方程更新 maxDP[i] 和 minDP[i]，同时用 maxDP[i] 更新全局最大值 result。

示例演算（nums = [2, 3, -2, 4]）：

• i=0: maxDP=2, minDP=2, result=2
• i=1: maxDP=max(3, 23, 23)=6, minDP=min(3, 23, 23)=3, result=6
• i=2: maxDP=max(-2, 6*(-2), 3*(-2))=-2 → 对比后取 max(-2, -12, -6)=-2? 错误！
  正确计算：
  maxDP = max(-2, 6*(-2)=-12, 3*(-2)=-6) = -2
  minDP = min(-2, 6*(-2)=-12, 3*(-2)=-6) = -12
  result = max(6, -2) = 6
• i=3: maxDP=max(4, -24=-8, -124=-48) = 4
  minDP=min(4, -24=-8, -124=-48) = -48
  result = max(6, 4) = 6

最终结果：6。

步骤 5：优化空间复杂度
由于 maxDP[i] 和 minDP[i] 仅依赖前一个状态，可用变量 maxVal 和 minVal 代替数组，将空间复杂度降至 O(1)。

最终代码框架（伪代码）：

maxVal = minVal = result = nums[0]
for i from 1 to n-1:
    if nums[i] < 0:
        swap(maxVal, minVal)  // 负数使大小关系反转
    maxVal = max(nums[i], maxVal * nums[i])
    minVal = min(nums[i], minVal * nums[i])
    result = max(result, maxVal)
return result