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

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

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

解题思路
这个问题与传统的最大子数组和问题不同，因为负数的存在会改变乘积的符号特性：

• 正数×正数=正数（增大乘积）
• 负数×负数=正数（可能从最小变成最大）
• 任何数×0=0（重置乘积）

因此我们需要同时跟踪当前区间的最大乘积和最小乘积。

详细解题步骤

1. 状态定义
定义两个DP数组：

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

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

• 从nums[i]重新开始（断开前面的子数组）
• 将nums[i]乘到前面的最大乘积子数组上
• 将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])

3. 初始化
maxDP[0] = minDP[0] = nums[0]
全局最大值result = nums[0]

4. 计算过程
以示例[2,3,-2,4]为例：

i=0：nums[0]=2
maxDP[0]=2, minDP[0]=2, result=2

i=1：nums[1]=3
maxDP[1] = max(3, 2×3, 2×3) = max(3,6,6)=6
minDP[1] = min(3, 2×3, 2×3) = min(3,6,6)=3
result = 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
result = 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
result = max(6,4)=6

5. 算法优化
由于每个状态只依赖于前一个状态，可以只用变量存储，空间复杂度O(1)：

def maxProduct(nums):
    if not nums: return 0
    
    max_prod = min_prod = result = nums[0]
    
    for i in range(1, len(nums)):
        # 临时存储，避免覆盖
        temp_max = max_prod
        temp_min = min_prod
        
        max_prod = max(nums[i], temp_max * nums[i], temp_min * nums[i])
        min_prod = min(nums[i], temp_max * nums[i], temp_min * nums[i])
        
        result = max(result, max_prod)
    
    return result

关键点总结

• 同时维护最大和最小乘积是解决负数问题的核心
• 状态转移时考虑三种可能性：重新开始、延续最大、延续最小
• 时间复杂度O(n)，空间复杂度可优化到O(1)
• 注意处理0的情况：遇到0时最大最小乘积都会重置