C++ 中最长递增子序列的数量
c++server side programmingprogramming
假设我们有一个未排序的整数数组。我们需要找出最长递增子序列的数量。如果输入为 [1, 3, 5, 4, 7]，则输出为 2，因为递增子序列分别为 [1,3,5,7] 和 [1, 3, 4, 7]
为了解决这个问题，我们将遵循以下步骤 −
- n := num 数组的大小，创建两个大小为 n 的数组 len 和 cnt，并用值 1 填充它们。
- lis := 1
- for i in range 1 to n
- for j in range 0 to i – 1
- if nums[i] > nums[j]，则
- if 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]
- lis := lis 和 len[j] 的最大值
- if nums[i] > nums[j]，则
- for j in range 0 to i – 1
- ans:= 0
- 对于 i 在 0 到 n 范围内 – 1
- 如果 len[i] = lis，则 ans := ans + cnt[j]
- return 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
