最長増加部分列(LIS)
(algorithm/longest_increasing_subsequence.hpp)

• View this file on GitHub
• Last update: 2022-09-02 13:25:33+09:00
• Include: #include "algorithm/longest_increasing_subsequence.hpp"

概要

• 最長増加部分列(LIS)をひとつ求める。

使い方

• longeset_incresing_subsequence(a): 数列 $\mathrm a$ の(狭義)最長増加部分列のうち辞書順最小であるものの添字を求める。

• longeset_incresing_subsequence(a, comp): 比較関数を comp としたときの最長増加部分列のうち辞書順最小であるものの添字を求める。

  (例) 広義の最長増加部分列を求めるには、comp = [](T x,T y) { return x <= y;} (または comp = std::less_equal<T>() )のようにする。

  計算量

• $\mathcal O(N\log N)$

Verified with

• test/aoj/DPL_1_D.test.cpp

Code

#pragma once
#include <vector>
template <typename T, class Compare>
std::vector<T> longest_increasing_subsequence(const std::vector<T> &a,
                                              Compare comp) {
    const int n = a.size();
    std::vector<T> dp;
    std::vector<int> id(n);
    for (int i = 0; i < n; i++) {
        typename std::vector<T>::iterator it =
            std::lower_bound(dp.begin(), dp.end(), a[i], comp);
        id[i] = std::distance(dp.begin(), it);
        if (it == dp.end()) {
            dp.push_back(a[i]);
        } else {
            *it = a[i];
        }
    }
    std::vector<T> lis(dp.size());
    for (int i = n - 1, j = lis.size() - 1; i >= 0; i--) {
        if (id[i] == j) {
            lis[j--] = i;
        }
    }
    return lis;
}
template <typename T>
std::vector<T> longest_increasing_subsequence(const std::vector<T> &a) {
    return longest_increasing_subsequence(a, std::less<T>());
}

#line 2 "algorithm/longest_increasing_subsequence.hpp"
#include <vector>
template <typename T, class Compare>
std::vector<T> longest_increasing_subsequence(const std::vector<T> &a,
                                              Compare comp) {
    const int n = a.size();
    std::vector<T> dp;
    std::vector<int> id(n);
    for (int i = 0; i < n; i++) {
        typename std::vector<T>::iterator it =
            std::lower_bound(dp.begin(), dp.end(), a[i], comp);
        id[i] = std::distance(dp.begin(), it);
        if (it == dp.end()) {
            dp.push_back(a[i]);
        } else {
            *it = a[i];
        }
    }
    std::vector<T> lis(dp.size());
    for (int i = n - 1, j = lis.size() - 1; i >= 0; i--) {
        if (id[i] == j) {
            lis[j--] = i;
        }
    }
    return lis;
}
template <typename T>
std::vector<T> longest_increasing_subsequence(const std::vector<T> &a) {
    return longest_increasing_subsequence(a, std::less<T>());
}

Back to top page