每日一道算法题

题目：最长递增子序列的个数

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1

• 输入：nums = [1,3,5,4,7]
• 输出：2
• 解释：有两个最长递增子序列，分别是 [1,3,4,7] 和 [1,3,5,7] 。

示例 2

• 输入：nums = [2,2,2,2,2]
• 输出：5
• 解释：最长递增子序列的长度是 1，并且存在 5 个长度为 1 的递增子序列，因此输出 5。

提示

• 1 <= nums.length <= 2000
• -10^6 <= nums[i] <= 10^6

解题思路提示

1. 状态定义：
   • 可以使用两个数组，dp 数组用来记录以每个位置结尾的最长递增子序列的长度，count 数组用来记录以每个位置结尾的最长递增子序列的个数。
2. 状态转移方程：
   • 对于每个位置 i ，遍历 0 到 i - 1 的位置 j ，如果 nums[i] > nums[j] ，则可以更新 dp[i] 和 count[i] 。
   • 更新 dp[i] ：dp[i] = max(dp[i], dp[j] + 1) 。
   • 更新 count[i] ：如果 dp[i] == dp[j] + 1 ，则 count[i] += count[j] ；如果 dp[i] < dp[j] + 1 ，则 count[i] = count[j] 。
3. 最终结果：
   • 遍历 dp 数组找到最长递增子序列的长度 maxLen 。
   • 再次遍历 count 数组，将所有对应 dp 值为 maxLen 的 count 值累加起来，得到最长递增子序列的个数.

 代码实现（Java）：

/*** ClassName:LongestIncreasingSubsequenceCount** @Author 爱掉头发的小李* @Create 2025/1/26 15:46* @Version 1.0*/
public class LongestIncreasingSubsequenceCount {public int findNumberOfLIS(int[] nums) {// 如果数组为空，直接返回 0if (nums == null || nums.length == 0) {return 0;}int n = nums.length;// dp 数组用于记录以每个位置结尾的最长递增子序列的长度，初始值都为 1int[] dp = new int[n];// count 数组用于记录以每个位置结尾的最长递增子序列的个数，初始值都为 1int[] count = new int[n];// 初始化 dp 数组和 count 数组for (int i = 0; i < n; i++) {dp[i] = 1;count[i] = 1;}// 填充 dp 数组和 count 数组for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {// 如果当前元素可以接在前面的元素后面形成更长的递增子序列if (dp[j] + 1 > dp[i]) {dp[i] = dp[j] + 1;count[i] = count[j];} else if (dp[j] + 1 == dp[i]) {// 如果长度相同，累加个数count[i] += count[j];}}}}// 找到最长递增子序列的长度int maxLength = 0;for (int len : dp) {maxLength = Math.max(maxLength, len);}// 计算最长递增子序列的个数int result = 0;for (int i = 0; i < n; i++) {if (dp[i] == maxLength) {result += count[i];}}return result;}public static void main(String[] args) {LongestIncreasingSubsequenceCount solution = new LongestIncreasingSubsequenceCount();int[] nums = {1, 3, 5, 4, 7};System.out.println(solution.findNumberOfLIS(nums));}
}

代码说明：

1. 初始化部分：

   • 首先检查输入数组 nums 是否为空或长度为 0，如果是则直接返回 0。
   • 初始化 dp 数组，将每个元素初始化为 1，因为每个元素自身可以构成一个长度为 1 的递增子序列。
   • 初始化 count 数组，同样将每个元素初始化为 1，表示以该元素结尾的长度为 1 的递增子序列的个数为 1。

2. 双重循环填充 dp 和 count 数组：

   • 外层循环遍历数组中的每个元素，从索引 1 开始。
   • 内层循环遍历当前元素之前的所有元素。
   • 如果当前元素 nums[i] 大于 nums[j]，说明可以将 nums[i] 接在以 nums[j] 结尾的递增子序列后面：
     • 如果 dp[j] + 1 大于 dp[i]，则更新 dp[i] 为 dp[j] + 1，并将 count[i] 更新为 count[j]，因为找到了更长的递增子序列。
     • 如果 dp[j] + 1 等于 dp[i]，说明找到了同样长度的递增子序列，将 count[i] 加上 count[j]。

3. 计算最长递增子序列的长度：

   • 遍历 dp 数组，找到其中的最大值 maxLength，即为最长递增子序列的长度。

4. 计算最长递增子序列的个数：

   • 再次遍历 dp 数组，将所有 dp[i] 等于 maxLength 的 count[i] 累加起来，得到最长递增子序列的个数。