区间动态规划例题：最大连续子序列乘积问题（带负数和零的版本）

题目描述
给定一个整数数组 nums，数组中可能包含正数、负数和零。请找出该数组中乘积最大的连续子序列（至少包含一个数），并返回其乘积。

示例：
输入：nums = [2, 3, -2, 4]
输出：6
解释：子数组 [2, 3] 的乘积为 6，是最大的连续子序列乘积。

解题思路
由于数组中存在负数，乘积的最大值可能由两个负数相乘得到（负负得正）。因此，我们需要同时记录以每个位置结尾的最大乘积和最小乘积（因为最小乘积乘以负数可能变成最大乘积）。

步骤分解

1. 状态定义
   定义两个动态规划数组：

   • maxDP[i]：表示以第 i 个元素结尾的连续子序列的最大乘积。
   • minDP[i]：表示以第 i 个元素结尾的连续子序列的最小乘积。

2. 状态转移方程
   对于每个位置 i（i ≥ 1）：

   • 如果当前数字 nums[i] 是正数，则：
     • 最大乘积可能是当前数本身，或当前数乘以前一个位置的最大乘积。
     • 最小乘积可能是当前数本身，或当前数乘以前一个位置的最小乘积。
   • 如果当前数字是负数，则：
     • 最大乘积可能是当前数本身，或当前数乘以前一个位置的最小乘积（因为负数乘小数可能得大数）。
     • 最小乘积可能是当前数本身，或当前数乘以前一个位置的最大乘积（因为负数乘大数可能得小数）。
   • 如果当前数字是零，则最大和最小乘积都会归零。

   综合上述情况，状态转移方程为：

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

3. 初始化
   对于第一个元素（i=0）：

   • maxDP[0] = nums[0]
   • minDP[0] = nums[0]
   • 全局最大值 globalMax 初始化为 nums[0]。

4. 遍历更新
   从 i=1 到 n-1 遍历数组，根据状态转移方程更新 maxDP[i] 和 minDP[i]，并同步更新全局最大值 globalMax。

5. 返回结果
   最终结果为 globalMax。

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

• i=0:
  maxDP[0] = 2, minDP[0] = 2, globalMax = 2

• i=1 (nums[1]=3):
  maxDP[1] = max(3, 2*3, 2*3) = 6
minDP[1] = min(3, 2*3, 2*3) = 3
globalMax = max(2, 6) = 6

• i=2 (nums[2]=-2):
  maxDP[2] = max(-2, 6*(-2), 3*(-2)) = max(-2, -12, -6) = -2
minDP[2] = min(-2, 6*(-2), 3*(-2)) = min(-2, -12, -6) = -12
globalMax = max(6, -2) = 6

• i=3 (nums[3]=4):
  maxDP[3] = max(4, -2*4, -12*4) = max(4, -8, -48) = 4
minDP[3] = min(4, -2*4, -12*4) = min(4, -8, -48) = -48
globalMax = max(6, 4) = 6

最终结果为 6。

复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组。
• 空间复杂度：O(n)，若优化状态存储可降至 O(1)。