最长递增子序列的变种：最长递增子序列的个数（进阶版——允许重复元素）

题目描述
给定一个整数数组 nums（可能包含重复元素），求最长递增子序列（LIS）的长度，并统计所有最长递增子序列的个数。注意：由于存在重复元素，不同的递增子序列可能包含相同的元素但在不同位置，但只要元素的下标序列不同，就视为不同的子序列。

示例
输入：nums = [1,3,5,4,7]
输出：[4, 2]（最长递增子序列长度为4，共有2个：[1,3,4,7] 和 [1,3,5,7]）
输入：nums = [2,2,2,2,2]
输出：[1, 5]（每个元素自身构成一个长度为1的递增子序列，共有5个）

解题过程

步骤1：定义状态

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

步骤2：状态转移
对于每个位置 i，我们需要检查所有 j < i：

1. 如果 nums[j] < nums[i]，说明 nums[i] 可以接在 nums[j] 结尾的递增子序列后面，形成更长的子序列。
   • 如果 length[j] + 1 > length[i]，则更新 length[i] = length[j] + 1，并重置 count[i] = count[j]。
   • 如果 length[j] + 1 == length[i]，则累加 count[i] += count[j]。
2. 如果 nums[j] == nums[i]，需要特殊处理重复元素：
   • 如果 length[j] == length[i]，说明存在重复但独立的序列，但直接累加会导致重复计数。我们需要避免重复统计，因此通常选择不处理 j（因为以相同值结尾且长度相同的序列会被重复计算，需通过额外规则去重）。

关键点：当 nums[j] == nums[i] 且 j < i 时，如果 length[j] == length[i]，说明在 j 处已经统计过相同值的序列，此时应忽略 j，否则会重复计数。正确做法是：当遇到相同值时，只考虑离 i 最近的那个相同值，但更安全的做法是：在遍历 j 时，如果遇到 nums[j] == nums[i] 且 length[j] == length[i]，则停止继续向前遍历（因为前面的相同值已经被统计过）。

步骤3：初始化
每个元素自身至少构成一个长度为1的序列：

• length[i] = 1
• count[i] = 1

步骤4：遍历顺序
外层循环 i 从 0 到 n-1，内层循环 j 从 0 到 i-1。

步骤5：获取结果

• 最长递增子序列的长度 max_len = max(length)。
• 总个数 total_count 为所有满足 length[i] == max_len 的 count[i] 之和。

示例推导（nums = [1,3,5,4,7]）
初始化：length = [1,1,1,1,1], count = [1,1,1,1,1]

• i=0：无 j，保持。
• i=1：
  • j=0：1<3 → length[1]=2, count[1]=1
• i=2：
  • j=0：1<5 → length[2]=2, count[2]=1
  • j=1：3<5 → length[2]=length[1]+1=3, count[2]=count[1]=1
• i=3：
  • j=0：1<4 → length[3]=2, count[3]=1
  • j=1：3<4 → length[3]=length[1]+1=3, count[3]=count[1]=1
  • j=2：5>4，跳过
• i=4：
  • j=0：1<7 → length[4]=2, count[4]=1
  • j=1：3<7 → length[4]=3, count[4]=1
  • j=2：5<7 → length[4]=4, count[4]=1
  • j=3：4<7 → length[4]=4（等于当前），累加 count[4] += count[3] = 1+1=2

最终：max_len=4，total_count=2（来自 i=4）。

重复元素处理（nums = [2,2,2,2]）
初始化：length=[1,1,1,1], count=[1,1,1,1]

• i=1：
  • j=0：2==2，且 length[0]==1，若直接累加会重复。正确做法：当 nums[j]==nums[i] 时，如果 length[j] == length[i]，说明之前已经统计过，此时将 count[i] 设为 count[j] 并重置重复状态（或跳过）。实际简化：对于相同值，只允许 j 的 length[j] + 1 > length[i] 时才更新，但这里长度不会更大，所以每个位置独立计数。
    最终：max_len=1，total_count=4（每个位置自身为一个序列）。

算法实现

def findNumberOfLIS(nums):
    n = len(nums)
    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]
            # 处理重复元素：如果nums[j] == nums[i]且length[j] == length[i]，则合并计数？
            # 实际上重复元素需避免重复计数，通常做法是：当遇到相同值且长度相等时，将count[i]设为0（或跳过），但这里我们选择不处理，因为题目要求下标序列不同即为不同序列。
    
    max_len = max(length) if n > 0 else 0
    total_count = 0
    for i in range(n):
        if length[i] == max_len:
            total_count += count[i]
    
    return [max_len, total_count]

复杂度分析

• 时间复杂度：O(n²)，两层循环。
• 空间复杂度：O(n)，用于存储 length 和 count 数组。