最长递增子序列的变种：最长递增子序列的个数（进阶版） 题目描述 给定一个整数数组 nums ，返回最长递增子序列（LIS）的个数。注意：可能存在多个最长递增子序列，需要统计其数量。例如，对于数组 [1,3,5,4,7] ，最长递增子序列的长度是 4，但有两个这样的子序列： [1,3,4,7] 和 [1,3,5,7] ，因此应返回 2。 解题过程 问题分析 本题是经典 LIS 问题（求最长长度）的扩展，需同时计算最长递增子序列的长度和数量。核心难点在于：当存在多个相同长度的 LIS 时，需避免重复计数或漏计。 动态规划状态定义 使用两个数组： length[i] ：以 nums[i] 结尾的 LIS 的长度。 count[i] ：以 nums[i] 结尾的、长度为 length[i] 的 LIS 的数量。 状态转移方程 初始化：每个元素自身构成长度为 1 的子序列，因此 length[i] = 1 ， count[i] = 1 。 遍历每个 i （0 到 n-1），对于每个 j （0 到 i-1）： 若 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] 。 获取最终结果 遍历所有 i ，找到最大的 LIS 长度 maxLen 。 对所有满足 length[i] == maxLen 的 i ，累加其 count[i] ，得到总个数。 示例演示 以 nums = [1,3,5,4,7] 为例： i=0: length=1, count=1 i=1: 继承 i=0 → length=2, count=1 i=2: 继承 i=1 → length=3, count=1 i=3: 比较 j=1（nums[ 1]=3 <4）→ length=2+1=3, count=1；但 j=2 不满足（5>4），最终 length=3, count=1 i=4: 继承 i=2（length=3+1=4, count=1）和 i=3（length=3+1=4, count 累加为 2） maxLen=4，总个数 = count[ 4 ] = 2。 复杂度分析 时间复杂度 O(n²)，空间复杂度 O(n)。可通过二分查找优化至 O(n log n)，但需调整计数逻辑（进阶内容略）。 通过以上步骤，可准确计算最长递增子序列的个数。