线性动态规划：最大连续子序列乘积的变种——计算乘积最大的连续子序列的个数

问题描述

给定一个整数数组 nums，数组中的元素可以是正整数、负整数或零。你需要计算乘积最大的连续子序列的个数。注意，乘积最大的连续子序列可能有多个，你需要统计这些子序列的个数。如果存在多个乘积最大的连续子序列，它们的乘积必须相等，且是所有连续子序列中最大的乘积。

示例 1：

输入：nums = [2, 3, -2, 4]
输出：2
解释：乘积最大的连续子序列有两个：[2, 3] 和 [4]，乘积都是6。

示例 2：

输入：nums = [-2, 0, -1]
输出：2
解释：乘积最大的连续子序列有两个：[0] 和 [-2, 0, -1]（乘积为0）。
注意：单个元素[0]的乘积是0，子序列[-2,0,-1]的乘积也是0，且这是最大乘积。

示例 3：

输入：nums = [1, 2, -3, 4, -5]
输出：3
解释：乘积最大的连续子序列有三个：[1, 2, -3, 4]（乘积24）、[2, -3, 4, -5]（乘积120）等等？实际上最大乘积是120，只有一个子序列乘积为120：[2, -3, 4, -5]。让我们计算：2*(-3)*4*(-5)=120。但[1,2,-3,4]乘积是-24，不是最大。所以输出应该是1。但示例假设是3，意味着可能有多个子序列乘积相同且最大，我们后面推导。

示例3的实际计算：

• 子序列[2, -3, 4, -5]：乘积=120
• 子序列[4, -5]：乘积=-20
• 子序列[-3, 4, -5]：乘积=60
• 子序列[2, -3, 4]：乘积=-24
• 子序列[-5]：乘积=-5
• 子序列[4]：乘积=4
  ...
  最大乘积是120，只有一个连续子序列得到120。所以示例3输出应该是1，但题目描述可能有误。我们以实际逻辑为准，目标是统计乘积最大的连续子序列个数。

解题思路

这是一个动态规划问题，与经典的“最大子数组乘积”问题相关。由于存在负数，乘积的最大值可能从之前的最小值（负数）翻转而来。因此我们需要同时记录以每个位置结尾的最大乘积和最小乘积，以及对应的个数。

状态定义：

• maxProd[i]：以第 i 个元素结尾的连续子序列的最大乘积。
• minProd[i]：以第 i 个元素结尾的连续子序列的最小乘积（因为负负得正，可能变成最大）。
• maxCount[i]：以第 i 个元素结尾的、乘积为 maxProd[i] 的连续子序列的个数。
• minCount[i]：以第 i 个元素结尾的、乘积为 minProd[i] 的连续子序列的个数。

状态转移：
对于每个位置 i，我们考虑是否将当前元素 nums[i] 加入前一个子序列，或者重新开始一个新的子序列（只包含当前元素）。状态转移分为两种情况：

1. 如果 nums[i] >= 0：

   • 最大乘积可能由前一个最大乘积乘以 nums[i] 得到，也可能只包含当前元素。
   • 即 maxProd[i] = max(maxProd[i-1] * nums[i], nums[i])
   • 类似地，最小乘积：minProd[i] = min(minProd[i-1] * nums[i], nums[i])

2. 如果 nums[i] < 0：

   • 最大乘积可能由前一个最小乘积（负数）乘以当前负数得到（负负得正），也可能只包含当前元素（但当前是负数，所以可能是最小）。
   • 即 maxProd[i] = max(minProd[i-1] * nums[i], nums[i])
   • 最小乘积：minProd[i] = min(maxProd[i-1] * nums[i], nums[i])

个数转移：
我们需要在更新乘积的同时更新个数。规则是：

• 如果某个乘积值是从前一个状态乘以当前数得到的，则个数继承前一个状态的个数。
• 如果某个乘积值等于当前数本身（即新开始一个子序列），则个数设为1。
• 如果两种方式得到相同的乘积值，则个数相加。

具体更新逻辑（以 nums[i] >= 0 为例）：

1. 候选1：maxProd[i-1] * nums[i]
2. 候选2：nums[i]
   比较候选1和候选2的值：

• 如果候选1 > 候选2：maxProd[i] = 候选1，maxCount[i] = maxCount[i-1]
• 如果候选1 < 候选2：maxProd[i] = 候选2，maxCount[i] = 1
• 如果候选1 == 候选2：maxProd[i] = 候选1，maxCount[i] = maxCount[i-1] + 1

类似地更新 minProd[i] 和 minCount[i]。

最终答案：
我们需要所有连续子序列中的最大乘积（全局最大乘积），然后统计所有以某个位置结尾的、乘积等于这个全局最大乘积的子序列个数之和。

即：

• 遍历过程中维护全局最大乘积 globalMax。
• 初始化 globalMax = nums[0]，answerCount = 1（因为初始时只有一个子序列，即第一个元素自身）。
• 在每一步更新状态后，如果 maxProd[i] == globalMax，则 answerCount += maxCount[i]。
• 如果 maxProd[i] > globalMax，则更新 globalMax = maxProd[i]，并重置 answerCount = maxCount[i]。

注意：如果 globalMax 是负数，则要考虑所有以该位置结尾的最大乘积子序列，但实际上全局最大乘积可能是0（如果有0存在），需要特别处理0的情况，因为0乘以任何数还是0。但我们的状态转移已经包含了0的情况。

详细步骤

让我们用示例1 nums = [2, 3, -2, 4] 来一步步推导：

初始状态（i=0）：

• maxProd[0] = 2, maxCount[0] = 1
• minProd[0] = 2, minCount[0] = 1
• globalMax = 2, answerCount = 1

i=1（nums[1]=3 >= 0）：
候选1（延伸）：maxProd[0]*3 = 2*3=6
候选2（新开始）：3
比较：6 > 3

• maxProd[1] = 6, maxCount[1] = maxCount[0] = 1
  候选1（最小）：minProd[0]*3 = 2*3=6
  候选2：3
  比较：6 > 3，所以最小乘积应该是3（更小）。
• minProd[1] = 3, minCount[1] = 1
  更新全局：maxProd[1]=6 > globalMax=2，所以 globalMax=6，answerCount = maxCount[1]=1

i=2（nums[2]=-2 < 0）：
最大乘积候选：
候选1（用前一个最小乘积乘当前负数）：minProd[1]*(-2) = 3*(-2) = -6
候选2（新开始）：-2
比较：-2 > -6，所以 maxProd[2] = -2, maxCount[2] = 1
最小乘积候选：
候选1（用前一个最大乘积乘当前负数）：maxProd[1]*(-2) = 6*(-2) = -12
候选2：-2
比较：-12 < -2，所以 minProd[2] = -12, minCount[2] = maxCount[1] = 1
更新全局：maxProd[2] = -2 < globalMax=6，全局不变。

i=3（nums[3]=4 >= 0）：
最大乘积候选：
候选1（延伸）：maxProd[2]*4 = (-2)*4 = -8
候选2（新开始）：4
比较：4 > -8，所以 maxProd[3] = 4, maxCount[3] = 1
最小乘积候选：
候选1（延伸）：minProd[2]*4 = (-12)*4 = -48
候选2：4
比较：-48 < 4，所以 minProd[3] = -48, minCount[3] = minCount[2] = 1
更新全局：maxProd[3]=4 < globalMax=6，全局不变。

最终，globalMax=6，answerCount=1，但示例1答案是2。为什么？因为我们漏掉了子序列[4]（乘积4）并不是最大乘积6。但[2,3]和[4]乘积都是6？不对，[4]乘积是4，不是6。实际上，示例1中最大乘积是6，只有一个子序列[2,3]乘积为6。但题目说输出2，说明可能我理解有误。让我们重新检查题目：它统计的是乘积最大的连续子序列的个数。在示例1中，乘积最大的连续子序列是[2,3]和[4]？但[4]乘积是4，不是6。所以示例1可能描述不准确，我们以逻辑为准，即最大乘积是6，只有一个子序列[2,3]得到6。但题目可能想表达的是：最大乘积可能是正数、负数或零。我们需要统计所有乘积最大的连续子序列的个数，包括乘积为0的情况。

实际上，示例2中最大乘积是0，有两个子序列乘积为0。所以我们的逻辑需要能处理多个最大乘积相同的情况。

在示例1中，最大乘积是6，只有[2,3]一个，所以输出应该是1。但题目说2，可能是笔误，我们以正确逻辑为准，即统计乘积最大的连续子序列个数。

算法实现

我们可以在一次遍历中完成计算，只需维护前一个状态，不需要完整数组。

伪代码：

初始化：
prevMax = nums[0], prevMin = nums[0]
prevMaxCount = 1, prevMinCount = 1
globalMax = nums[0]
answerCount = 1

for i from 1 to n-1:
    curr = nums[i]
    if curr >= 0:
        候选max1 = prevMax * curr, 候选max2 = curr
        如果max1 > max2:
            currMax = max1, currMaxCount = prevMaxCount
        否则如果max1 < max2:
            currMax = max2, currMaxCount = 1
        否则: # 相等
            currMax = max1, currMaxCount = prevMaxCount + 1

        候选min1 = prevMin * curr, 候选min2 = curr
        类似更新currMin和currMinCount（取小）
    else: # curr < 0
        候选max1 = prevMin * curr, 候选max2 = curr
        更新currMax和currMaxCount
        候选min1 = prevMax * curr, 候选min2 = curr
        更新currMin和currMinCount

    # 更新全局
    如果currMax > globalMax:
        globalMax = currMax
        answerCount = currMaxCount
    否则如果currMax == globalMax:
        answerCount += currMaxCount

    # 更新前一个状态
    prevMax = currMax, prevMin = currMin
    prevMaxCount = currMaxCount, prevMinCount = currMinCount
返回 answerCount

边界情况

1. 数组长度为1：直接返回1。
2. 数组中有0：0乘以任何数为0，所以最大乘积可能是0。如果所有元素都是负数，最大乘积可能是负数（例如[-1, -2]最大乘积是2，因为负负得正）。
3. 多个子序列乘积相同且最大：如示例2，两个0乘积子序列。

验证示例

我们用示例2：nums = [-2, 0, -1]

初始化：

• prevMax=-2, prevMin=-2, prevMaxCount=1, prevMinCount=1
• globalMax=-2, answerCount=1

i=1: curr=0 >=0
候选max1 = (-2)0=0, 候选max2=0
相等，所以 currMax=0, currMaxCount=1+1=2? 注意：这里新开始子序列[0]是一个，延伸前一个子序列得到[-2,0]乘积0是另一个，所以个数是2。
候选min1 = (-2)0=0, 候选min2=0
相等，currMin=0, currMinCount=1+1=2
更新全局：currMax=0 > globalMax=-2，所以globalMax=0, answerCount=currMaxCount=2

i=2: curr=-1 <0
候选max1 = prevMin * curr = 0*(-1)=0, 候选max2=-1
0 > -1，所以currMax=0, currMaxCount=prevMinCount=2
候选min1 = prevMax * curr = 0*(-1)=0, 候选min2=-1
-1 < 0，所以currMin=-1, currMinCount=1
更新全局：currMax=0 == globalMax=0，所以answerCount += currMaxCount = 2+2=4
最终answerCount=4？但示例2输出是2。这里我们发现，我们重复计数了。实际上，以i=2结尾的最大乘积子序列有两个乘积为0：一个是[0]（但[0]在i=1时已经统计过了），另一个是[-2,0,-1]？乘积是0。但[0]被重复统计了，因为i=2时currMaxCount=2表示以i=2结尾的乘积为0的子序列有两个：[-2,0,-1]和[0,-1]？但[0,-1]乘积是0吗？0*(-1)=0，是的。所以确实有多个。

但题目要求的是“连续子序列”，且不同的子序列只要区间不同就是不同的。所以[-2,0,-1]、[0]、[0,-1]都是乘积为0的连续子序列，但示例2输出是2，说明它只统计了[0]和[-2,0,-1]？可能题目中“连续子序列”指的是连续子数组，且相同乘积但不同区间算不同。但示例2中乘积为0的子序列有：[-2,0]、[0]、[0,-1]、[-2,0,-1]共4个。输出2意味着它只统计了长度为1的[0]和长度为3的[-2,0,-1]。但[-2,0]和[0,-1]的乘积也是0，为什么不算？这可能是因为“最大乘积”可能对应多个值，但题目可能定义“乘积最大的连续子序列”为乘积最大的值对应的子序列，但可能有多个子序列乘积相同且最大。在示例2中最大乘积是0，有4个子序列乘积为0，但示例输出2，说明题目可能只统计那些“以某个位置结尾的、且不能再延伸的”子序列？不对，题目没有这样说。

实际上，这是一个常见陷阱：题目可能是要求“乘积最大的连续子序列的个数”，但示例2的官方解释是：[0]和[-2,0,-1]两个。这说明他们只统计了“整个数组”和“单个0”这两个子序列。但[-2,0]和[0,-1]也是乘积0，为什么不算？因为[-2,0]是[-2,0,-1]的子序列，而最大乘积子序列如果存在包含关系，可能只算最长的？但题目没有明确。

经过查阅，类似问题（LeetCode 1567. Maximum Length of Subarray With Positive Product）是统计乘积为正的最长子数组长度，不是统计个数。本题是自定义变种。所以我们以逻辑自洽为主：统计所有连续子数组中乘积等于全局最大乘积的个数，不同区间算不同。

那么对于示例2：
所有连续子数组：
[-2] -> -2
[-2,0] -> 0
[-2,0,-1] -> 0
[0] -> 0
[0,-1] -> 0
[-1] -> -1
乘积最大是0，有4个子数组乘积为0。所以答案应该是4。但示例说2，可能题目是统计“最长”的乘积最大子序列个数？或只统计那些“非严格扩展”的？我们不纠结示例，以描述为准。

修正逻辑

由于题目描述可能不清晰，我们按照最合理的解释：统计所有连续子数组中乘积等于全局最大乘积的个数。那么我们需要在动态规划中累计所有位置结尾的符合条件的个数，最后求和。

但注意，这样会重复计数吗？不会，因为每个子数组有唯一的右端点，我们以右端点结尾计数，覆盖所有子数组。

但全局最大乘积可能出现在多个右端点，我们需要把每个右端点对应的个数加起来。

所以最终答案就是：answerCount 累计所有 maxProd[i]==globalMax 时的 maxCount[i] 之和。

对于示例2：
i=1: maxProd=0, globalMax更新为0，answerCount=2
i=2: maxProd=0, globalMax仍为0，answerCount+=2，得到4。
所以输出4。

但题目示例输出2，说明可能题目是统计“不同的子序列”个数，且不考虑子序列的包含关系。由于题目是自定义变种，我们按照常见理解实现即可。

最终代码框架（Python）

def countMaxProductSubsequences(nums):
    n = len(nums)
    if n == 0:
        return 0
    
    prev_max = nums[0]
    prev_min = nums[0]
    prev_max_count = 1
    prev_min_count = 1
    
    global_max = nums[0]
    ans_count = 1  # 初始第一个元素
    
    for i in range(1, n):
        curr = nums[i]
        if curr >= 0:
            # 计算当前最大乘积和个数
            cand1 = prev_max * curr
            cand2 = curr
            if cand1 > cand2:
                curr_max = cand1
                curr_max_count = prev_max_count
            elif cand1 < cand2:
                curr_max = cand2
                curr_max_count = 1
            else:  # 相等
                curr_max = cand1
                curr_max_count = prev_max_count + 1
            
            # 计算当前最小乘积和个数
            cand1 = prev_min * curr
            cand2 = curr
            if cand1 < cand2:
                curr_min = cand1
                curr_min_count = prev_min_count
            elif cand1 > cand2:
                curr_min = cand2
                curr_min_count = 1
            else:
                curr_min = cand1
                curr_min_count = prev_min_count + 1
        else:  # curr < 0
            # 最大乘积来自前一个最小乘积（负数）乘当前负数
            cand1 = prev_min * curr
            cand2 = curr
            if cand1 > cand2:
                curr_max = cand1
                curr_max_count = prev_min_count
            elif cand1 < cand2:
                curr_max = cand2
                curr_max_count = 1
            else:
                curr_max = cand1
                curr_max_count = prev_min_count + 1
            
            # 最小乘积来自前一个最大乘积乘当前负数
            cand1 = prev_max * curr
            cand2 = curr
            if cand1 < cand2:
                curr_min = cand1
                curr_min_count = prev_max_count
            elif cand1 > cand2:
                curr_min = cand2
                curr_min_count = 1
            else:
                curr_min = cand1
                curr_min_count = prev_max_count + 1
        
        # 更新全局最大乘积和答案计数
        if curr_max > global_max:
            global_max = curr_max
            ans_count = curr_max_count
        elif curr_max == global_max:
            ans_count += curr_max_count
        
        # 更新前一个状态
        prev_max, prev_min = curr_max, curr_min
        prev_max_count, prev_min_count = curr_max_count, curr_min_count
    
    return ans_count

复杂度分析

• 时间复杂度：O(n)，只需一次遍历。
• 空间复杂度：O(1)，只用了常数个变量。

总结

本题是最大子数组乘积问题的变种，增加了统计个数的要求。关键是在动态规划中同时维护最大/最小乘积以及对应的个数，并在状态转移时正确处理个数继承和相加的情况。最后统计所有乘积等于全局最大乘积的子序列个数。注意处理正数、负数和零的情况，以及乘积相等时的个数累加。