Tăng chuỗi con trong C ++

Giả sử chúng ta có một mảng số nguyên, nhiệm vụ của chúng ta là tìm tất cả các dãy con tăng dần khác nhau của mảng đã cho và độ dài của dãy con tăng dần phải ít nhất là 2. Vì vậy, nếu mảng giống như [4,6,7,7 ], thì đầu ra sẽ có dạng - [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7 , 7], [7,7], [4,7,7]].

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

• Xác định một mảng, được gọi là res để lưu trữ tất cả các kết quả
• Thực hiện một phương pháp được gọi là giải quyết. Điều này sẽ lấy mảng nums, mảng bắt đầu và mảng tạm thời
• nếu kích thước của nhiệt độ> 1, thì hãy chèn nhiệt độ vào res
• tạo một tập hợp được gọi là đã ghé thăm
• đối với tôi trong phạm vi bắt đầu có kích thước là nums
  • x:=nums [i]
  • nếu x trong tập hợp đã truy cập, thì bỏ qua phần tiếp theo của vòng lặp
  • chèn x vào nhóm đã truy cập
  • nếu tạm thời trống hoặc phần tử cuối cùng của tạm thời <=x, thì
    • chèn x vào tạm thời
    • gọi giải quyết (nums, i + 1, temp)
    • xóa một phần tử khỏi kết thúc tạm thời
• Từ phương thức chính, gọi giải quyết (nums, 0, temp)
• trả lại res

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector < vector <int> > res;
   void solve( vector <int>& nums, int start, vector <int> temp){
      if(temp.size() > 1){
         res.push_back(temp);
      }
      set <int> visited;
      for(int i = start; i < nums.size(); i++){
         int x = nums[i];
         if(visited.count(x))continue;
         visited.insert(x);
         if(temp.empty() || temp[temp.size() - 1] <= x){
            temp.push_back(x);
            solve(nums, i + 1, temp);
            temp.pop_back();
         }
      }
   }
   vector<vector<int>> findSubsequences(vector<int>& nums) {
      res.clear();
      vector <int> temp;
      solve(nums, 0, temp);
      return res;
   }
};
main(){
   vector<int> v = {5,6,7,8};
   Solution ob;
   print_vector(ob.findSubsequences(v));
}

Đầu vào

[4,6,7,8]

Đầu ra

[[5, 6, ],[5, 6, 7, ],[5, 6, 7, 8, ],[5, 6, 8, ],[5, 7, ],[5, 7, 8, ],[5, 8, ],[6, 7, ],[6, 7, 8, ],[6, 8, ],[7, 8, ],]