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
以上是 C ++中最长的递增子序列数 的全部内容， 来源链接： utcz.com/z/338321.html
