区间动态规划例题：最大子数组和的乘积版本（乘积最大子数组）

题目描述
给定一个整数数组 nums（可能包含负数），找出一个连续子数组，使得子数组内所有数的乘积最大，返回该最大乘积。例如：

• 输入：[2, 3, -2, 4]，输出：6（子数组 [2, 3] 的乘积为 6）
• 输入：[-2, 0, -1]，输出：0（子数组 [0] 或 [-2, 0] 的乘积为 0）

关键难点
由于负数的存在，当前的最大乘积可能由之前的最小乘积（负数）乘以当前负数得到。因此需同时记录以每个位置结尾的最大乘积和最小乘积。

解题步骤

1. 定义状态

   • 设 dp_max[i] 表示以第 i 个元素结尾的连续子数组的最大乘积。
   • 设 dp_min[i] 表示以第 i 个元素结尾的连续子数组的最小乘积。

2. 状态转移方程
   对于每个位置 i，考虑三种情况：

   • 仅取当前数 nums[i]
   • 当前数 × 以前一个位置结尾的最大乘积（dp_max[i-1] * nums[i]）
   • 当前数 × 以前一个位置结尾的最小乘积（dp_min[i-1] * nums[i]）

   因此：

   dp_max[i] = max(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])
   dp_min[i] = min(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])
   

3. 初始化

   • dp_max[0] = dp_min[0] = nums[0]（只有一个元素时，乘积为其本身）

4. 遍历与更新

   • 从 i = 1 到 n-1 遍历数组，更新 dp_max 和 dp_min。
   • 同时用变量 global_max 记录遍历过程中的最大乘积。

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

   • i=0: dp_max=2, dp_min=2, global_max=2
   • i=1:
     • 候选值：3, 2×3=6, 2×3=6 → dp_max=6
     • 候选值：3, 6, 6 → dp_min=3
     • global_max=max(2,6)=6
   • i=2:
     • 候选值：-2, 6×(-2)=-12, 3×(-2)=-6 → dp_max=-2
     • 候选值：-2, -12, -6 → dp_min=-12
     • global_max=6
   • i=3:
     • 候选值：4, -2×4=-8, -12×4=-48 → dp_max=4
     • 候选值：4, -8, -48 → dp_min=-48
     • global_max=6
   • 最终结果：6

复杂度分析

• 时间复杂度：O(n)，只需一次遍历。
• 空间复杂度：O(1)（可优化为只保留前一个状态，无需完整数组）。

总结
通过同时维护最大和最小乘积，有效处理了负数带来的符号变化问题，确保在遍历过程中不漏掉潜在的最大乘积解。