最长递增子序列的个数 (Number of Longest Increasing Subsequence)

题目描述

给定一个整数数组 nums，你需要计算最长递增子序列（Longest Increasing Subsequence, LIS）的个数。
注意：可能存在多个不同的最长递增子序列，但它们必须是严格递增的（即子序列中相邻元素严格递增）。
你需要返回满足“长度为最长递增子序列长度”的子序列个数。

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

1. [1, 3, 5, 7]
2. [1, 3, 4, 7]

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

解题思路

这是一个经典的线性动态规划问题。我们不仅要记录“以每个位置结尾的最长递增子序列长度”，还要记录“以每个位置结尾的最长递增子序列的个数”。

核心步骤：

1. 定义两个数组：
   • length[i]：表示以 nums[i] 结尾的最长递增子序列的长度。
   • count[i]：表示以 nums[i] 结尾的、长度为 length[i] 的递增子序列的个数。
2. 从左到右遍历数组，对于每个位置 i，我们检查它前面的所有元素 j（j < i）：
   • 如果 nums[j] < nums[i]，说明可以将 nums[i] 接在以 nums[j] 结尾的递增子序列后面，形成一个新的递增子序列。
   • 我们需要更新 length[i] 和 count[i]，具体规则会在下面详细解释。
3. 遍历过程中，始终维护一个全局的“最长递增子序列长度” max_len，以及“所有长度等于 max_len 的子序列个数之和” total_count。

详细步骤

步骤 1：初始化

• 初始化 length 数组，length[i] = 1。因为每个元素自身可以构成一个长度为 1 的递增子序列。
• 初始化 count 数组，count[i] = 1。因为每个元素自身构成一个递增子序列的方式只有 1 种。
• 初始化全局变量：
  • max_len = 1（至少为 1）
  • total_count = 0（先设为 0，最后计算）

步骤 2：动态规划递推

对于每个 i 从 0 到 n-1（n 是数组长度）：

• 遍历所有 j 从 0 到 i-1：
  • 如果 nums[j] < nums[i]：
    • 此时，如果 length[j] + 1 > length[i]，说明找到了一个更长的递增子序列以 nums[i] 结尾。
      更新 length[i] = length[j] + 1，并且重置 count[i] = count[j]（因为现在找到了更长的，之前存储的个数就无效了，重新开始计数）。
    • 如果 length[j] + 1 == length[i]，说明找到了另一个同样长度的最长递增子序列以 nums[i] 结尾。
      那么将 count[j] 累加到 count[i] 上（即：count[i] += count[j]）。
• 在更新完所有 j 后，比较 length[i] 与 max_len：
  • 如果 length[i] > max_len，则更新 max_len = length[i]，并且重置 total_count = count[i]（因为之前存储的总个数是基于更短的 LIS 的，现在要重新计算）。
  • 如果 length[i] == max_len，则将 count[i] 累加到 total_count 上。

步骤 3：举例推导

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

• i=0, nums[0]=1:
  length[0]=1, count[0]=1
  max_len=1, total_count=1

• i=1, nums[1]=3:
  j=0: nums[0] < 3, length[0]+1=2 > length[1]=1 → length[1]=2, count[1]=count[0]=1
  max_len=2, total_count=1

• i=2, nums[2]=5:
  j=0: 1<5, length[0]+1=2 > length[2]=1 → length[2]=2, count[2]=count[0]=1
  j=1: 3<5, length[1]+1=3 > length[2]=2 → length[2]=3, count[2]=count[1]=1
  max_len=3, total_count=1

• i=3, nums[3]=4:
  j=0: 1<4, length[0]+1=2 > length[3]=1 → length[3]=2, count[3]=count[0]=1
  j=1: 3<4, length[1]+1=3 > length[3]=2 → length[3]=3, count[3]=count[1]=1
  j=2: 5>=4, 跳过
  max_len=3, total_count=1+1=2（因为 length[3]=3 等于 max_len，所以累加 count[3]=1）

• i=4, nums[4]=7:
  j=0: 1<7, length[0]+1=2 > length[4]=1 → length[4]=2, count[4]=count[0]=1
  j=1: 3<7, length[1]+1=3 > length[4]=2 → length[4]=3, count[4]=count[1]=1
  j=2: 5<7, length[2]+1=4 > length[4]=3 → length[4]=4, count[4]=count[2]=1
  j=3: 4<7, length[3]+1=4 == length[4]=4 → count[4] += count[3]=1+1=2
  length[4]=4 > max_len=3 → 更新 max_len=4, total_count=count[4]=2

最终结果：total_count=2。

步骤 4：边界情况

• 所有元素相同：每个 length[i]=1, count[i]=1，max_len=1，total_count 等于数组长度。
• 数组严格递增：每个 length[i] 都不同，每个 count[i]=1，max_len 等于数组长度，total_count=1。

步骤 5：复杂度

• 时间复杂度：O(n²)，因为对于每个 i 都要遍历所有 j < i。
• 空间复杂度：O(n)，存储 length 和 count 数组。

代码框架（Python）

def findNumberOfLIS(nums):
    n = len(nums)
    length = [1] * n
    count = [1] * n
    max_len = 1
    total_count = 0
    
    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]
        if length[i] > max_len:
            max_len = length[i]
            total_count = count[i]
        elif length[i] == max_len:
            total_count += count[i]
    
    return total_count

思考与变种

1. 如果要求输出所有的最长递增子序列（而不仅仅是计数），就需要在动态规划过程中记录路径，这会增加空间复杂度，但思路类似。
2. 可以用树状数组优化到 O(n log n) 的时间复杂度，但需要处理多个相同长度的 LIS 计数，较为复杂。
3. 如果允许非严格递增（即允许相等），只需将判断条件 nums[j] < nums[i] 改为 nums[j] <= nums[i]，但要注意 count 的计算逻辑可能变化。

这个问题的难点在于同时维护长度和个数，并在更新长度时正确重置个数。通过上述步骤，可以准确计算出最长递增子序列的总数。