test/src/dp/longest_increasing_subsequence/longest_increasing_subsequence.test.cpp

• View this file on GitHub
• Last update: 2022-07-26 15:37:13+09:00
• Problem: https://judge.yosupo.jp/problem/longest_increasing_subsequence

Depends on

• Longest Increasing Subsequence (library/dp/longest_increasing_subsequence.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence"

#include <iostream>

#include "library/dp/longest_increasing_subsequence.hpp"

using suisen::longest_increasing_subsequence;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (auto &e : a) std::cin >> e;

    std::vector<int> lis = longest_increasing_subsequence(a);
    
    const int k = lis.size();
    std::cout << k << std::endl;
    for (int i = 0; i < k; ++i) {
        std::cout << lis[i];
        if (i + 1 != k) std::cout << ' ';
    }
    std::cout << std::endl;

    return 0;
}

#line 1 "test/src/dp/longest_increasing_subsequence/longest_increasing_subsequence.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence"

#include <iostream>

#line 1 "library/dp/longest_increasing_subsequence.hpp"



#include <algorithm>
#include <vector>

namespace suisen {
    namespace internal::lis {
        template <typename T, typename ComparatorType>
        std::vector<int> solve(const std::vector<T>& a) {
            if (a.empty()) return {};
            const int n = a.size();
            std::vector<T> dp;
            dp.reserve(n);
            std::vector<int> pd(n, -1), id(n, -1);
            for (int i = 0; i < n; ++i) {
                const int pos = std::lower_bound(dp.begin(), dp.end(), a[i], ComparatorType{}) - dp.begin();
                id[pos] = i;
                if (pos >= 1) pd[i] = id[pos - 1];
                if (pos == int(dp.size())) dp.push_back(a[i]);
                else dp[pos] = a[i];
            }
            int len = dp.size();
            std::vector<int> ans(len);
            for (int cur = id[len - 1]; cur >= 0; cur = pd[cur]) ans[--len] = cur;
            return ans;
        }
    }
    // @returns ** indices ** of longest increasing subsequence
    template <typename T>
    std::vector<int> longest_increasing_subsequence(const std::vector<T>& a)    { return internal::lis::solve<T, std::less<T>>(a); }
    // @returns ** indices ** of longest nondecreasing subsequence
    template <typename T>
    std::vector<int> longest_nondecreasing_subsequence(const std::vector<T>& a) { return internal::lis::solve<T, std::less_equal<T>>(a); }
    // @returns ** indices ** of longest nonincreasing subsequence
    template <typename T>
    std::vector<int> longest_nonincreasing_subsequence(const std::vector<T>& a) { return internal::lis::solve<T, std::greater_equal<T>>(a); }
    // @returns ** indices ** of longest decreasing subsequence
    template <typename T>
    std::vector<int> longest_decreasing_subsequence(const std::vector<T>& a)    { return internal::lis::solve<T, std::greater<T>>(a); }
} // namespace suisen


#line 6 "test/src/dp/longest_increasing_subsequence/longest_increasing_subsequence.test.cpp"

using suisen::longest_increasing_subsequence;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (auto &e : a) std::cin >> e;

    std::vector<int> lis = longest_increasing_subsequence(a);
    
    const int k = lis.size();
    std::cout << k << std::endl;
    for (int i = 0; i < k; ++i) {
        std::cout << lis[i];
        if (i + 1 != k) std::cout << ' ';
    }
    std::cout << std::endl;

    return 0;
}

Back to top page