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