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