最长递增子序列的个数 题目描述 给定一个整数数组 nums ，找到最长递增子序列（LIS）的长度，并返回最长递增子序列的个数。注意：可能存在多个最长递增子序列，你需要计算所有不同的最长递增子序列的数量。 示例： 输入：nums = [ 1,3,5,4,7 ] 输出：2 解释：有两个最长递增子序列，分别是 [ 1, 3, 4, 7] 和 [ 1, 3, 5, 7 ]，长度均为 4。 解题过程 步骤1：定义状态 我们需要同时跟踪两个信息： length[i] ：以 nums[i] 结尾的最长递增子序列的长度。 count[i] ：以 nums[i] 结尾的最长递增子序列的个数。 步骤2：状态转移 对于每个位置 i ，我们需要检查所有 j < i ： 如果 nums[j] < nums[i] ，说明 nums[i] 可以接在以 nums[j] 结尾的子序列后面。 比较 length[j] + 1 与 length[i] ： 如果 length[j] + 1 > length[i] ，说明找到更长的子序列，更新 length[i] = length[j] + 1 ，并重置 count[i] = count[j] 。 如果 length[j] + 1 == length[i] ，说明找到相同长度的不同子序列，累加 count[i] += count[j] 。 步骤3：初始化 每个元素本身至少构成一个长度为1的子序列： length[i] = 1 （至少包含自己） count[i] = 1 （至少有一种方式） 步骤4：计算过程 以 nums = [1,3,5,4,7] 为例： | i | nums[ i] | length[ i] | count[ i ] | 说明 | |---|---------|-----------|----------|------| | 0 | 1 | 1 | 1 | 初始化 | | 1 | 3 | 2 | 1 | 接在 i=0 后 | | 2 | 5 | 3 | 1 | 接在 i=1 后 | | 3 | 4 | 3 | 1 | 接在 i=1 后（长度3与i=2相同，但路径独立） | | 4 | 7 | 4 | 2 | 可接在 i=2 或 i=3 后，两者长度相同，累加计数 | 步骤5：统计结果 最大长度 max_len = max(length) = 4。 对所有满足 length[i] == max_len 的 i ，累加其 count[i] ： 这里只有 i=4 满足条件， count[4] = 2 ，故最终结果为 2。 步骤6：复杂度分析 时间复杂度：O(n²)，需要两层循环遍历。 空间复杂度：O(n)，用于存储 length 和 count 数组。 通过以上步骤，我们同时跟踪了最长递增子序列的长度和数量，确保了正确计数所有可能的最长序列。