每日一道算法题

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

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

示例 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) {
        // 如果数组为空，直接返回 0
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        // dp 数组用于记录以每个位置结尾的最长递增子序列的长度，初始值都为 1
        int[] dp = new int[n];
        // count 数组用于记录以每个位置结尾的最长递增子序列的个数，初始值都为 1
        int[] 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] 累加起来，得到最长递增子序列的个数。