最长递增子序列的个数（进阶版：考虑重复元素及每个序列的具体构成统计）

题目描述

给定一个整数数组 nums，请统计数组中最长递增子序列（Longest Increasing Subsequence, LIS）的总个数。注意，如果有多个最长递增子序列，但它们包含的元素下标集合相同（即使元素值可能相同，但由于下标不同，也视为不同的子序列），则分别计数。题目要求返回最长递增子序列的个数。

示例 1：
输入：nums = [1,3,5,4,7]
输出：2
解释：有两个最长递增子序列：[1, 3, 4, 7] 和 [1, 3, 5, 7]，长度均为4。

示例 2：
输入：nums = [2,2,2,2,2]
输出：5
解释：最长递增子序列长度为1，每个元素单独构成的子序列都是，因此共有5个。

进阶要求：不仅要统计个数，还需考虑重复元素的存在，并确保不重不漏地统计所有下标不同的最长递增子序列。

解题思路

此题是经典“最长递增子序列”问题的进阶版本，核心目标是在求解LIS长度的同时，统计达到该长度的子序列个数。难点在于：当存在重复元素时，如何避免重复计数，以及如何正确累加不同路径的个数。我们将使用动态规划，设计两个数组：

• length[i]：以 nums[i] 结尾的最长递增子序列的长度。
• count[i]：以 nums[i] 结尾，且长度为 length[i] 的递增子序列的个数。

关键点：对于每个位置 i，我们需要检查所有 j < i：

1. 如果 nums[j] < nums[i]，说明 nums[i] 可以接在 nums[j] 结尾的子序列后面。
2. 如果接上后新序列长度等于当前记录的 length[i]，则增加计数；如果大于，则更新长度并重置计数。

注意：可能存在多个不同的 j 产生相同长度的序列，我们需要将它们的 count[j] 累加起来。但要注意避免重复统计：例如数组 [1,1,1,2]，当 i=3（值为2）时，前面三个1都能接上，但每个1对应的子序列是独立的（下标不同），因此需要分别累加。

逐步讲解

步骤1：定义状态

• length[i]：以第 i 个元素结尾的最长递增子序列的长度。
• count[i]：以第 i 个元素结尾，且长度恰好为 length[i] 的递增子序列的个数。

初始化：每个元素自身至少构成一个长度为1的子序列，所以 length[i] = 1，count[i] = 1。

步骤2：状态转移

对于每个 i 从 0 到 n-1：

• 对于每个 j 从 0 到 i-1：
  • 如果 nums[j] < nums[i]，说明 nums[i] 可以接在 nums[j] 之后。
    • 新长度 = length[j] + 1。
    • 比较新长度与当前 length[i]：
      1. 如果 length[j] + 1 > length[i]：
         • 更新 length[i] = length[j] + 1。
         • 重置 count[i] = count[j]（因为找到了更长的序列，计数从当前 j 的计数开始）。
      2. 如果 length[j] + 1 == length[i]：
         • 说明找到了另一组相同长度的序列，累计计数：count[i] += count[j]。
      3. 如果 length[j] + 1 < length[i]：忽略（不会产生更优解）。

例子：nums = [1,3,5,4,7]

• i=0: length[0]=1, count[0]=1
• i=1: j=0, nums[0]=1<3 → length[0]+1=2 > length[1]=1 → 更新 length[1]=2, count[1]=count[0]=1
• i=2: j=0,1 都能接，但 j=1 产生更长序列 length=3，最终 length[2]=3, count[2]=1
• i=3: 重点看 j=1 (nums[1]=3<4, length[1]=2+1=3) 和 j=2 (nums[2]=5>4 不满足)。
  与 j=1 接上后新长度3 > 当前 length[3]=1 → 更新 length[3]=3, count[3]=count[1]=1。
• i=4: 需要检查所有 j<4：
  • j=0: 1<7 → length[0]+1=2
  • j=1: 3<7 → length[1]+1=3
  • j=2: 5<7 → length[2]+1=4
  • j=3: 4<7 → length[3]+1=4
    其中最大长度是4（来自 j=2 和 j=3），且这两个都产生长度4，所以 count[4] = count[2] + count[3] = 1 + 1 = 2。

最终最长长度 maxLen = 4，对应结尾下标 i=4，count[4]=2，所以总个数为2。

步骤3：统计结果

• 首先遍历得到全局最长长度 maxLen。
• 然后遍历所有 i，如果 length[i] == maxLen，则将对应的 count[i] 累加到答案中。

注意：如果存在多个不同的结尾下标，它们的 length[i] 都等于 maxLen，则都需要累加，因为它们代表不同的最长递增子序列（结尾元素不同）。

步骤4：处理重复元素

上述方法天然处理了重复元素，因为我们是按下标区分子序列的。即使 nums[i] == nums[j]，只要 i ≠ j，并且 nums[j] < nums[i] 不成立（因为相等不满足严格递增），就不会错误累加。因此重复元素不会导致重复计数问题。

示例验证：nums = [2,2,2,2,2]
每个位置 length[i]=1, count[i]=1。
最长长度 maxLen=1，累加所有 count[i]=5，输出5，正确。

复杂度分析

• 时间复杂度：O(n²)，因为对每个 i 需要检查前面所有 j。
• 空间复杂度：O(n)，用于存储 length 和 count 数组。

代码实现（Python）

def findNumberOfLIS(nums):
    n = len(nums)
    if n == 0:
        return 0
    
    length = [1] * n
    count = [1] * n
    
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                if length[j] + 1 > length[i]:
                    length[i] = length[j] + 1
                    count[i] = count[j]
                elif length[j] + 1 == length[i]:
                    count[i] += count[j]
    
    max_len = max(length)
    ans = 0
    for i in range(n):
        if length[i] == max_len:
            ans += count[i]
    
    return ans

示例运行

以 nums = [1,3,5,4,7] 为例：

• 初始化 length = [1,1,1,1,1], count = [1,1,1,1,1]
• 完成动态规划后：
  length = [1,2,3,3,4]
  count = [1,1,1,1,2]
• max_len = 4，只有 i=4 满足，累加 count[4]=2 → 输出2。

扩展思考

1. 如果题目要求输出所有最长递增子序列的具体内容，而不仅仅是计数，该如何修改？
   （提示：可以额外记录每个位置的前驱列表，然后通过回溯生成所有序列。）
2. 如果数组长度非常大（例如 n=2000），O(n²) 会超时，有没有更优的解法？
   （提示：可以使用树状数组或线段树优化到 O(n log n)，但需要处理累加计数，较为复杂。）

这个题目结合了“最长递增子序列”和“计数”两个经典动态规划问题，通过两个状态数组的配合，清晰地区分了长度和个数，并能正确处理重复元素的情况。