Longest Increasing Subsequence (最長増加部分列) (dp/longest-increasing-subsequence.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-08-10 06:35:14+00:00
• Include: #include "dp/longest-increasing-subsequence.hpp"

最長増加部分列(LIS)の長さを求める。

lis[i] を、現状態で長さ $i$ 以下の増加部分列を作るときの最後の要素の最小値と定義する。このとき lis[i] は常に単調増加になっている。

数列の要素を左からみる。二分探索で lis[k] が現在の要素以下(未満) となる最大の $k$ を求め、lis[k+1] を現在の要素に書き換えることを繰り返すことで LIS を求めることができる。

ここでは実装しない(←実装しなさーい！)が別のアルゴリズムとして、lis[i] を現状態で最後の要素が値 $i$ の増加部分列を作るときの最長の長さと定義する方法も存在する。数列の要素を左から見ていって、現在の値の要素以下(未満) で最大の lis[k] $+ 1$ を求めることで更新出来て、これは BIT や セグメント木を使って効率的に求めることができる。

longest_increasing_subsequence

size_t longest_increasing_subsequence(const vector<T>& a, bool strict)

数列 a の最長増加部分列の長さを求める。strict が true のとき狭義(厳密に増加する列)、false のとき広義で求める。

計算量

• $O(N \log N)$

Verified with

• test/verify/aoj-dpl-1-d.test.cpp

Code

#pragma once

#include <algorithm>
#include <cstddef>
#include <vector>

template <typename T>
std::size_t longest_increasing_subsequence(const std::vector<T>& a,
                                           bool strict) {
  std::vector<T> lis;
  for (auto& p : a) {
    typename std::vector<T>::iterator it;
    if (strict)
      it = std::lower_bound(lis.begin(), lis.end(), p);
    else
      it = std::upper_bound(lis.begin(), lis.end(), p);
    if (lis.end() == it)
      lis.emplace_back(p);
    else
      *it = p;
  }
  return lis.size();
}

#line 2 "dp/longest-increasing-subsequence.hpp"

#include <algorithm>
#include <cstddef>
#include <vector>

template <typename T>
std::size_t longest_increasing_subsequence(const std::vector<T>& a,
                                           bool strict) {
  std::vector<T> lis;
  for (auto& p : a) {
    typename std::vector<T>::iterator it;
    if (strict)
      it = std::lower_bound(lis.begin(), lis.end(), p);
    else
      it = std::upper_bound(lis.begin(), lis.end(), p);
    if (lis.end() == it)
      lis.emplace_back(p);
    else
      *it = p;
  }
  return lis.size();
}

Back to top page