最大连续子序列乘积问题

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

解题过程

这个问题之所以不能简单地套用最大子数组和（Kadane算法）的思路，是因为乘积具有特殊性：一个负数乘以一个负数会变成正数。这意味着，在遍历数组时，我们不仅要记录以当前元素结尾的最大乘积，还要记录最小乘积（可能是负数），因为如果后续遇到负数，这个最小乘积可能会变成最大乘积。

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

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

2. 状态转移方程
   对于每个位置i（i≥1），我们需要考虑三种情况：

   • 如果nums[i]是正数，那么：
     • 最大乘积可能是maxDP[i-1] * nums[i]（延续之前的乘积）
     • 或者是nums[i]本身（从头开始）
   • 如果nums[i]是负数，那么：
     • 最大乘积可能是minDP[i-1] * nums[i]（负数乘以负数变成正数）
     • 或者是nums[i]本身
   • 如果nums[i]是0，那么最大和最小乘积都是0

   综合起来，状态转移方程为：

   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. 初始条件
   当i=0时（第一个元素）：

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

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

   i=0: nums[0]=2

   • maxDP[0] = 2
   • minDP[0] = 2

   i=1: nums[1]=3

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

   i=2: nums[2]=-2

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

   i=3: nums[3]=4

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

   全局最大值在遍历过程中记录：max(2,6,-2,4)=6

5. 算法优化
   实际上，我们可以只用两个变量来记录前一个状态，而不需要完整的DP数组：

   def maxProduct(nums):
       if not nums:
           return 0
   
       max_so_far = min_so_far = result = nums[0]
   
       for i in range(1, len(nums)):
           # 临时保存当前值，因为max_so_far会被更新
           temp_max = max_so_far
           max_so_far = max(nums[i], max_so_far * nums[i], min_so_far * nums[i])
           min_so_far = min(nums[i], temp_max * nums[i], min_so_far * nums[i])
           result = max(result, max_so_far)
   
       return result
   

6. 时间复杂度分析
   该算法只需要遍历一次数组，时间复杂度为O(n)，空间复杂度为O(1)（优化后版本）。

关键点总结

• 必须同时记录最大和最小乘积，因为负数可能翻转大小关系
• 每个位置有三种可能：从当前位置重新开始、延续最大乘积、延续最小乘积
• 最终结果是所有maxDP[i]中的最大值，而不是最后一个值

这种方法能够正确处理所有情况，包括正数、负数和0的混合情况。