673.最长子序列的数量
题目描述
给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 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。
提示：
- 0 <= nums.length <= 2000
- -10^6 <= nums[i] <= 10^6
题目解析
这道题是 Leetcode 300. 最长递增子序列的进阶版本，我们不仅要找到最长子序列，还要找到最长子序列的个数。写该题之间建议先完成 Leetcode 300. 最长递增子序列。我们在以前的博客中已经详细介绍过寻找最长递增子序列的算法。
接下来，我们对算法进行改造，以解决这个更为复杂的问题。
在原来的算法中，我们维护一个数组dp[i],表示nums中前i个元素的最长递增子序列的长度。我们对dp数组进行更新，具体的更新规则如下：
- 如果
nums[i] > nums[j], 且dp[j] + 1 > dp[i], 则dp[i] = dp[j] + 1,0 <= j < i。 - 否则，
dp[i] = dp[i]。
现在，我们不仅需要知道，nums中前i个元素的最长递增子序列的长度，还需要知道，nums中前i个元素的最长递增子序列的个数。
我们可以维护一个数组count[i],表示nums中前i个元素的最长递增子序列的个数。我们对count数组进行更新，具体的更新规则如下：
- 如果
nums[i] > nums[j], 且dp[j] + 1 == dp[i], 则count[i] += count[j],0 <= j < i。这表示当前长度为dp[i]的最长递增子序列，可以由前j个元素的最长递增子序列延伸得到。 - 如果
nums[i] > nums[j], 且dp[j] + 1 > dp[i]，则count[i] = count[j]。这表示当前dp[i]并不是以nums[i]结尾的最长递增子序列，最长递增子序列长度应该更新为dp[j] + 1。那么count[i] = count[j]，表示当前长度为dp[j]+1的最长递增子序列，只能由前j个元素的最长递增子序列延伸得到。
这样，我们就得到了nums中前i个元素的最长递增子序列长度和对应的最长子序列的个数。
接下来，只要将dp数组中最大的元素（即最长子序列的长度），在count数组中对应的值累加起来，就可以得到nums中最长递增子序列的个数。
复杂度分析：
- 时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)，其中
n是数组nums的长度。 - 空间复杂度：
O
(
n
)
O(n)
O(n)，其中
n是数组nums的长度。
代码实现
Go版本：
func findNumberOfLIS(nums []int) int {
n:=len(nums) // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
dp:=make([]int,n) // cnt[i] 表示以 nums[i] 结尾的、长度为 dp[i] 的递增子序列的个数
cnt:=make([]int,n)
maxLen:=1
cnt[0]=1
dp[0]=1
for i:=1;i<n;i++{
cnt[i]=1
dp[i]=1
for j:=0;j<i;j++{
if(nums[i]>nums[j]){
if(dp[i]==dp[j]+1){
cnt[i]+=cnt[j]
}else if(dp[i]<dp[j]+1){
cnt[i]=cnt[j]
dp[i]=max(dp[i],dp[j]+1)
}
}
}
maxLen=max(maxLen,dp[i])
}
res:=0
for i:=0;i<n;i++{
if(dp[i]==maxLen){
res+=cnt[i]
}
}
return res
}
Python版本：
class Solution(object):
def findNumberOfLIS(self, nums):
n = len(nums)
dp = [1] * n # dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
cnt = [1] * n # cnt[i] 表示以 nums[i] 结尾的、长度为 dp[i] 的递增子序列的个数
max_len = 1
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
if dp[i] == dp[j] + 1:
cnt[i] += cnt[j]
elif dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
cnt[i] = cnt[j]
max_len = max(max_len, dp[i])
res = 0
for i in range(n):
if dp[i] == max_len:
res += cnt[i]
return res
C++版本：
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1); // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
vector<int> cnt(n, 1); // cnt[i] 表示以 nums[i] 结尾的、长度为 dp[i] 的递增子序列的个数
int max_len = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
if (dp[i] == dp[j] + 1) {
cnt[i] += cnt[j];
} else if (dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
cnt[i] = cnt[j];
}
}
}
max_len = max(max_len, dp[i]);
}
int res = 0;
for (int i = 0; i < n; ++i) {
if (dp[i] == max_len) {
res += cnt[i];
}
}
return res;
}
};