C ++中最长的递增子序列数
假设我们有一个未排序的整数数组。我们必须找到最长递增子序列的数量，因此，如果输入类似于[1、3、5、4、4、7]，则输出将为2，因为递增子序列是[1、3、5、7]和[1、3、4、7]
为了解决这个问题，我们将遵循以下步骤-
n：=num数组的大小，创建两个大小为n的len和cnt数组，并用值1填充它们。
lis：=1
对于我在1到n范围内
如果nums[i]>nums[j]，则
lis：=lis和len的最大值[j]
如果len[j]+1>len[i]，则len[i]：=len[j]+1和cnt[i]：=cnt[j]
否则，当len[j]+1=len[j]时，则cnt[i]：=cnt[i]+cnt[j]
对于0到i–1范围内的j
回答：=0
对于i，范围为0至n–1
如果len[i]=lis，则ans：=ans+cnt[j]
返回ans
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
vector <int> len(n, 1), cnt(n, 1);
int lis = 1;
for(int i = 1; i < n; i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
if(len[j] + 1 > len[i]){
len[i] = len[j] + 1;
cnt[i] = cnt[j];
}
else if(len[j] + 1 == len[i]){
cnt[i] += cnt[j];
}
}
lis = max(lis, len[i]);
}
}
int ans = 0;
for(int i = 0; i < n; i++){
if(len[i] == lis)ans += cnt[i];
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,3,5,4,7};
cout << (ob.findNumberOfLIS(v));
}输入项
[1,3,5,4,7]
输出结果
2