673. 最长递增子序列的个数

🟠   🔖  树状数组 线段树 数组 动态规划  🔗 力扣 LeetCode

题目

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Example 1:

Input: nums = [1,3,5,4,7]

Output: 2

Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: nums = [2,2,2,2,2]

Output: 5

Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.

Constraints:

• 1 <= nums.length <= 2000
• -10^6 <= nums[i] <= 10^6
• The answer is guaranteed to fit inside a 32-bit integer.

题目大意

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

示例 1:

输入: [1,3,5,4,7]

输出: 2

解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

输入: [2,2,2,2,2]

输出: 5

解释: 最长递增子序列的长度是 1，并且存在 5 个子序列的长度为 1，因此输出 5。

提示:

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

解题思路

1. 定义 dp 数组

   • dp[i][0]：表示以 nums[i] 结尾的 最长递增子序列长度。
   • dp[i][1]：表示以 nums[i] 结尾的 最长递增子序列的个数。
   • 初始化 dp[i] = [1, 1]，因为单个元素本身就是一个长度为 1 的递增子序列，个数为 1。

2. 双层循环构建 dp

   • 遍历 nums[i] 之前的所有 nums[j]，如果 nums[i] > nums[j]，说明 nums[i] 可以接在 nums[j] 后面形成更长的递增子序列。
   • 更新 dp[i] 的最长长度：
     • 如果 dp[j][0] + 1 > dp[i][0]，说明找到了更长的递增子序列，更新 dp[i] = [dp[j][0] + 1, dp[j][1]]。
     • 如果 dp[j][0] + 1 == dp[i][0]，说明找到了相同长度的递增子序列，需要累加 dp[i][1]。

3. 更新全局最长递增子序列长度

   • 维护 maxLen 记录 dp[i][0] 中的最大值。

4. 计算最终结果

   • 遍历 dp 数组，统计 dp[i][1]，其中 dp[i][0] == maxLen，即所有 最长递增子序列的个数 之和。

复杂度分析

• 时间复杂度：O(n^2)，双层遍历 nums，每个元素与前面所有元素进行比较。
• 空间复杂度：O(n)，需要 dp 数组存储每个位置的最长递增子序列信息。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumberOfLIS = function (nums) {
	const n = nums.length;
	if (n === 0) return 0;

	// dp[i][0] = 以 nums[i] 结尾的最长递增子序列长度
	// dp[i][1] = 以 nums[i] 结尾的最长递增子序列个数
	const dp = Array.from({ length: n }, () => [1, 1]);
	let maxLen = 1;

	for (let i = 0; i < n; i++) {
		for (let j = 0; j < i; j++) {
			if (nums[i] > nums[j]) {
				if (dp[i][0] < dp[j][0] + 1) {
					dp[i] = [dp[j][0] + 1, dp[j][1]];
				} else if (dp[i][0] === dp[j][0] + 1) {
					dp[i][1] += dp[j][1];
				}
			}
		}
		maxLen = Math.max(maxLen, dp[i][0]);
	}

	// 统计所有最长子序列的个数
	return dp.reduce(
		(total, [length, count]) => total + (length === maxLen ? count : 0),
		0
	);
};

相关题目

题号	标题	题解	标签	难度	力扣
300	最长递增子序列	[✓]	数组 二分查找 动态规划	🟠	🀄️ 🔗
674	最长连续递增序列	[✓]	数组	🟢	🀄️ 🔗
2407	最长递增子序列 II		树状数组 线段树 队列 4+	🔴	🀄️ 🔗