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

题目描述
给定一个整数数组nums（可能包含正数、负数和0），找出该数组中连续子序列的最大乘积。例如，给定数组[2,3,-2,4]，最大乘积子序列是[2,3]，乘积为6。

解题过程

步骤1：理解问题特性

• 与最大子数组和问题不同，乘积运算具有特殊性
• 负数乘以负数会得到正数，最小值可能突然变成最大值
• 遇到0时乘积会重置为0
• 需要同时跟踪最大乘积和最小乘积

步骤2：定义状态
定义两个DP数组：

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

步骤3：状态转移方程
对于每个位置i（i ≥ 1）：

1. 如果nums[i] > 0：

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

2. 如果nums[i] < 0：

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

3. 如果nums[i] = 0：

   • maxDP[i] = 0
   • minDP[i] = 0

步骤4：边界条件

• maxDP[0] = nums[0]
• minDP[0] = nums[0]

步骤5：算法实现

def maxProduct(nums):
    if not nums:
        return 
    
    n = len(nums)
    maxDP = [0] * n
    minDP = [0] * n
    maxDP[0] = minDP[0] = nums[0]
    result = nums[0]
    
    for i in range(1, n):
        if nums[i] > 0:
            maxDP[i] = max(nums[i], maxDP[i-1] * nums[i])
            minDP[i] = min(nums[i], minDP[i-1] * nums[i])
        elif nums[i] < 0:
            maxDP[i] = max(nums[i], minDP[i-1] * nums[i])
            minDP[i] = min(nums[i], maxDP[i-1] * nums[i])
        else:
            maxDP[i] = minDP[i] = 0
        
        result = max(result, maxDP[i])
    
    return result

步骤6：空间优化
由于每个状态只依赖于前一个状态，可以优化空间复杂度：

def maxProduct_optimized(nums):
    if not nums:
        return 0
    
    maxProd = minProd = result = nums[0]
    
    for i in range(1, len(nums)):
        if nums[i] < 0:
            maxProd, minProd = minProd, maxProd
        
        maxProd = max(nums[i], maxProd * nums[i])
        minProd = min(nums[i], minProd * nums[i])
        result = max(result, maxProd)
    
    return result

步骤7：示例分析
以nums = [2,3,-2,4]为例：

• i=0: max=2, min=2, result=2
• i=1: max=max(3,2×3)=6, min=min(3,2×3)=3, result=6
• i=2: 负数交换→max=max(-2,3×-2)=-2, min=min(-2,6×-2)=-12, result=6
• i=3: max=max(4,-2×4)=4, min=min(4,-12×4)=-48, result=6

最终结果为6。

关键洞察

• 同时维护最大和最小值是解决乘积类问题的核心
• 遇到负数时，最大值和最小值会互换角色
• 空间优化版本更简洁高效，时间复杂度O(n)，空间复杂度O(1)