最長増加部分列

概要

${a_i}$ から順番を変えずにいくつかの要素を取り除いた列 ${b_i}$ であって $i < j$ なら $b_i < b_j$ (または $b_i \leq b_j$) をみたすもののうち，長さが最大のものを最長増加部分列 (Longest Increasing Subsequence; LIS) という．

計算量

$O(N\log N)$

実装

template <class Array>
Array lis(const Array &x) {
    size_t n = x.size();
    const int INF = std::numeric_limits<decltype(x[0])>::max();
    Array dp(n, INF);
    for (size_t i = 0; i < n; i++) {
        *std::upper_bound(dp.begin(), dp.begin() + n, x[i]) = x[i];  // a_i <= a_j
        // *lower_bound(dp.begin(), dp.begin() + n, x[i]) = x[i]; // a_i < a_j
    }
    return Array(dp.begin(), std::lower_bound(dp.begin(), dp.begin() + n, INF));
}

検証

たくさん

参考文系

蟻本