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

难度：中等

给定一个未排序的整数数组 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$

💡思路：动态规划

定义 dp 数组，dp[i] 表示 nums 中前 i（包括 nums[i] ）最长递增子序列的长度；

并定义 count 数组，表示以 nums[i] 为结尾的字符串，最长递增子序列的个数为 count[i]。

• 遍历 nums 数组，当遍历 nums[i] 时，将nums[i]与 [0, i - 1] 中的数进行比较，当 nums[i] > nums[j]时：

  • 如果 dp[j] + 1 > dp[i]，说明找到了一个更长的递增子序列，则更新 dp[i] = dp[j] + 1 ，此时以 j 为结尾的子串的最长递增子序列的个数，就是最新的以 i 为结尾的子串的最长递增子序列的个数，即：count[i] = count[j] 。
  • dp[j] + 1 == dp[i]，说明找到了两个相同长度的递增子序列，那么以 i 为结尾的子串的最长递增子序列的个数 就应该加上以 j 为结尾的子串的最长递增子序列的个数，即：count[i] += count[j] 。

• 题目要求最长递增序列的长度的个数，我们定义一个变量 maxCount 把最长长度记录下来；

• 最后统计所有等于 maxCount长度的 数量。

🍁代码：(C++、Java)

C++

class Solution {
public:int findNumberOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();int n = nums.size();vector<int> dp(n, 1); //i之前（包括i）最长递增子序列的长度vector<int> count(n, 1); //以nums[i]为结尾的字符串，最长递增子序列的个数int maxCount = 0;for(int i = 0; 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];}if (dp[i] > maxCount) maxCount = dp[i];}}int result = 0;for (int i = 0; i < n; i++) {if (maxCount == dp[i]) result += count[i];}return result;}
};

Java

class Solution {public int findNumberOfLIS(int[] nums) {int n = nums.length;if(n <= 1) return n;int dp[] = new int[n]; //i之前（包括i）最长递增子序列的长度Arrays.fill(dp, 1);int count[] = new int[n]; //以nums[i]为结尾的字符串，最长递增子序列的个数Arrays.fill(count, 1);int maxCount = 0;for(int i = 0; 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];}if (dp[i] > maxCount) maxCount = dp[i];}}int result = 0;for (int i = 0; i < n; i++) {if (maxCount == dp[i]) result += count[i];}return result;}
}

🚀 运行结果：

🕔 复杂度分析：

• 时间复杂度：$O(n^2)$，其中 n 为数组 nums的长度。
• 空间复杂度：$O(n)$。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我LeetCode主页 / CSDN—力扣专栏，每日更新！

注： 如有不足，欢迎指正！