LIS
(math/longest_increasing_subsequence.hpp)

• View this file on GitHub
• Last update: 2023-07-29 00:51:20+09:00
• Include: #include "math/longest_increasing_subsequence.hpp"

説明

与えられた数列に対して、最長増加部分列となる添え字の列構築する。narrowly が true のとき狭義単調増加、 false のとき広義単調増加の場合に対して構築する。$O(N\log N)$

Verified with

• test/math/Longest_Increasing_Subsequence.test.cpp

Code

#pragma once

#include <algorithm>
#include <limits>
#include <vector>

namespace ebi {

template <class T> std::vector<T> LIS(const std::vector<T> &a, bool narrowly) {
    std::vector<T> ret = {std::numeric_limits<T>::max()};
    std::vector<int> used;
    used.reserve(a.size());
    for (auto x : a) {
        auto itr = narrowly ? std::lower_bound(ret.begin(), ret.end(), x)
                            : std::upper_bound(ret.begin(), ret.end(), x);
        used.emplace_back(itr - ret.begin());
        if (itr == ret.end())
            ret.emplace_back(x);
        else
            *itr = x;
    }
    int len = ret.size();
    int idx = len - 1;
    T now = std::numeric_limits<T>::max();
    std::vector<int> lis(len);
    for (int i = int(a.size()) - 1; i >= 0; i--) {
        if (used[i] == idx && a[i] + int(narrowly) <= now) {
            now = a[i];
            lis[idx--] = i;
        }
    }
    return lis;
}

}  // namespace ebi

#line 2 "math/longest_increasing_subsequence.hpp"

#include <algorithm>
#include <limits>
#include <vector>

namespace ebi {

template <class T> std::vector<T> LIS(const std::vector<T> &a, bool narrowly) {
    std::vector<T> ret = {std::numeric_limits<T>::max()};
    std::vector<int> used;
    used.reserve(a.size());
    for (auto x : a) {
        auto itr = narrowly ? std::lower_bound(ret.begin(), ret.end(), x)
                            : std::upper_bound(ret.begin(), ret.end(), x);
        used.emplace_back(itr - ret.begin());
        if (itr == ret.end())
            ret.emplace_back(x);
        else
            *itr = x;
    }
    int len = ret.size();
    int idx = len - 1;
    T now = std::numeric_limits<T>::max();
    std::vector<int> lis(len);
    for (int i = int(a.size()) - 1; i >= 0; i--) {
        if (used[i] == idx && a[i] + int(narrowly) <= now) {
            now = a[i];
            lis[idx--] = i;
        }
    }
    return lis;
}

}  // namespace ebi

Back to top page