Số chuỗi con tăng dài nhất trong C ++

Giả sử chúng ta có một mảng số nguyên chưa được sắp xếp. chúng ta phải tìm số lượng dãy con tăng dài nhất, vì vậy nếu đầu vào là [1, 3, 5, 4, 7], thì đầu ra sẽ là 2, vì dãy con tăng dần là [1,3,5,7] và [1, 3, 4, 7]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng num, tạo hai mảng len và cnt có kích thước n và điền chúng bằng giá trị 1.
• lis:=1
• cho tôi trong phạm vi từ 1 đến n
  • cho j trong phạm vi từ 0 đến i - 1
    • nếu nums [i]> nums [j], thì
      • if len [j] + 1> len [i], then len [i]:=len [j] + 1 và cnt [i]:=cnt [j]
      • ngược lại khi len [j] + 1 =len [j], thì cnt [i]:=cnt [i] + cnt [j]
    • lis:=max của lis và len [j]
• ans:=0
• cho tôi trong phạm vi từ 0 đến n - 1
  • if len [i] =lis, then ans:=ans + cnt [j]
• trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[1,3,5,4,7]

Đầu ra

2