区间动态规划例题：最大连续子序列乘积问题

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

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

解题过程

这个问题看似简单，但有一个关键难点：负数的存在。由于负负得正，当前的最小乘积（可能是负数）在遇到另一个负数时，可能会变成最大乘积。因此我们需要同时记录最大乘积和最小乘积。

步骤1：定义状态

我们定义两个DP数组：

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

步骤2：状态转移方程

对于每个位置i，我们有三种选择：

1. 只包含当前元素nums[i]
2. 将当前元素与前面的最大乘积子数组连接：nums[i] × maxDP[i-1]
3. 将当前元素与前面的最小乘积子数组连接：nums[i] × minDP[i-1]

因此状态转移方程为：
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：初始化

对于第一个元素：
maxDP[0] = nums[0]
minDP[0] = nums[0]

步骤4：计算过程

让我们通过示例nums = [2,3,-2,4]来演示：

i=0：

• maxDP[0] = 2
• minDP[0] = 2
• 当前最大值：2

i=1：

• 候选值：3, 3×2=6, 3×2=6
• maxDP[1] = max(3,6,6) = 6
• minDP[1] = min(3,6,6) = 3
• 当前最大值：max(2,6) = 6

i=2：

• 候选值：-2, -2×6=-12, -2×3=-6
• maxDP[2] = max(-2,-12,-6) = -2
• minDP[2] = min(-2,-12,-6) = -12
• 当前最大值：max(6,-2) = 6

i=3：

• 候选值：4, 4×(-2)=-8, 4×(-12)=-48
• maxDP[3] = max(4,-8,-48) = 4
• minDP[3] = min(4,-8,-48) = -48
• 最终结果：max(6,4) = 6

步骤5：空间优化

由于我们只需要前一个状态的值，可以用变量代替数组：

def maxProduct(nums):
    if not nums:
        return 0
    
    max_prod = min_prod = result = nums[0]
    
    for i in range(1, len(nums)):
        # 保存临时值，因为max_prod会在计算min_prod时被改变
        temp_max = max_prod
        temp_min = min_prod
        
        max_prod = max(nums[i], nums[i] * temp_max, nums[i] * temp_min)
        min_prod = min(nums[i], nums[i] * temp_max, nums[i] * temp_min)
        
        result = max(result, max_prod)
    
    return result

复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组
• 空间复杂度：O(1)，只使用了常数级别的额外空间

这个算法的关键在于同时跟踪最大和最小乘积，以处理负数相乘可能产生更大正数的情况。