最长递增子序列的个数（进阶版） 题目描述 给定一个整数数组 nums ，找到最长递增子序列（LIS）的长度，并计算最长递增子序列的个数。注意：可能存在多个最长递增子序列，你需要统计所有不同的最长递增子序列的数量。 示例 输入： nums = [1,3,5,4,7] 输出： [最长递增子序列长度, 个数] = [4, 2] 最长递增子序列有两个： [1,3,5,7] 和 [1,3,4,7] ，长度均为 4。 解题过程 步骤 1：定义状态数组 length[i] ：以 nums[i] 结尾的最长递增子序列的长度。 count[i] ：以 nums[i] 结尾的最长递增子序列的个数。 步骤 2：初始化 每个元素本身至少构成一个长度为 1 的子序列： length[i] = 1 （至少包含自己） count[i] = 1 （至少有一种方式构成子序列） 步骤 3：状态转移 遍历每个位置 i ，并检查所有前面的位置 j (0 ≤ j < i) ： 如果 nums[j] < nums[i] ，说明 nums[i] 可以接在 nums[j] 后面形成更长的递增子序列。 比较当前长度： 如果 length[j] + 1 > length[i] ： 更新 length[i] = length[j] + 1 重置 count[i] = count[j] （因为找到了更长的序列，计数从 j 继承） 如果 length[j] + 1 == length[i] ： 说明找到相同长度的新路径，累加计数： count[i] += count[j] 步骤 4：统计最终结果 遍历所有 i ，找到最大的 length[i] ，记为 max_len 。 将所有 length[i] == max_len 的 count[i] 累加，得到总个数。 示例推导（nums = [ 1,3,5,4,7]） | i | nums[ i] | length[ i] | count[ i ] | 解释 | |---|---------|-----------|----------|------| | 0 | 1 | 1 | 1 | 初始化 | | 1 | 3 | 2 | 1 | 接在 i=0 后，长度=1+1=2 | | 2 | 5 | 3 | 1 | 接在 i=1 后，长度=2+1=3 | | 3 | 4 | 3 | 1 | 接在 i=1 后，长度=2+1=3 | | 4 | 7 | 4 | 2 | 可接在 i=2（长度3→4）或 i=3（长度3→4），累加 count=1+1=2 | 最大长度 max_len = 4 ，对应 i=4 ，总个数 count[4] = 2 。 最终结果： [4, 2] ✅