Advertisement
Derga

Untitled

Feb 24th, 2023
635
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. std::vector<int> longest_increasing_subseq(const std::vector<int>& seq) {
  8.   int numbers_count = seq.size();
  9.   vector<int> subseq;
  10.   vector<int> subseq_indexes;
  11.   vector<int> trace(numbers_count, -1);
  12.   for (int i = 0; i < numbers_count; ++i) {
  13.     if (subseq.empty() || subseq.back() < seq[i]) {
  14.       if (!subseq.empty())
  15.         trace[i] = subseq_indexes.back();
  16.       subseq.push_back(seq[i]);
  17.       subseq_indexes.push_back(i);
  18.     } else {
  19.       int idx = lower_bound(subseq.begin(), subseq.end(), seq[i]) - subseq.begin();
  20.       if (idx > 0) {
  21.         trace[i] = subseq_indexes[idx - 1];
  22.       }
  23.       subseq[idx] = seq[i];
  24.       subseq_indexes[idx] = i;
  25.     }
  26.   }
  27.  
  28.   vector<int> path;
  29.   int idx = subseq_indexes.back();
  30.  
  31.   while (idx != -1) {
  32.     path.push_back(seq[idx]);
  33.     idx = trace[idx];
  34.   }
  35.   reverse(path.begin(), path.end());
  36.   return path;
  37. }
  38.  
  39. int main() {
  40.   std::ios_base::sync_with_stdio(false);
  41.   std::cin.tie(nullptr);
  42.  
  43.   std::size_t n;
  44.   cin >> n;
  45.   std::vector<int> seq(n);
  46.  
  47.   for (auto& el : seq) {
  48.     std::cin >> el;
  49.   }
  50.  
  51.   auto longest_seq = longest_increasing_subseq(seq);
  52.  
  53.   std::cout << longest_seq.size() << "\n";
  54.   for (auto el : longest_seq) {
  55.     std::cout << el << " ";
  56.   }
  57.  
  58.   return 0;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement