Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <vector>
- using namespace std;
- std::vector<int> longest_increasing_subseq(const std::vector<int>& seq) {
- int numbers_count = seq.size();
- vector<int> subseq;
- vector<int> subseq_indexes;
- vector<int> trace(numbers_count, -1);
- for (int i = 0; i < numbers_count; ++i) {
- if (subseq.empty() || subseq.back() < seq[i]) {
- if (!subseq.empty())
- trace[i] = subseq_indexes.back();
- subseq.push_back(seq[i]);
- subseq_indexes.push_back(i);
- } else {
- int idx = lower_bound(subseq.begin(), subseq.end(), seq[i]) - subseq.begin();
- if (idx > 0) {
- trace[i] = subseq_indexes[idx - 1];
- }
- subseq[idx] = seq[i];
- subseq_indexes[idx] = i;
- }
- }
- vector<int> path;
- int idx = subseq_indexes.back();
- while (idx != -1) {
- path.push_back(seq[idx]);
- idx = trace[idx];
- }
- reverse(path.begin(), path.end());
- return path;
- }
- int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
- std::size_t n;
- cin >> n;
- std::vector<int> seq(n);
- for (auto& el : seq) {
- std::cin >> el;
- }
- auto longest_seq = longest_increasing_subseq(seq);
- std::cout << longest_seq.size() << "\n";
- for (auto el : longest_seq) {
- std::cout << el << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement