最長増加部分列 (longest increasing subsequence)
(include/emthrm/dynamic_programming/longest_increasing_subsequence.hpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Include: #include "emthrm/dynamic_programming/longest_increasing_subsequence.hpp"

$i < j$ を満たす任意の $i, j$ に対して $A_i < A_j$ を満たす部分列 $A$ の内、最長のものである。

時間計算量

$O(N\log{N})$

仕様

名前	戻り値	備考
template <bool IS_STRICT = true, typename T> std::vector<T> longest_increasing_subsequence(const std::vector<T>& a);	$A$ の最長増加部分列	IS_STRICT は広義単調増加であるかを表す。

参考文献

• Craige Schensted: Longest Increasing and Decreasing Subsequences, Canadian Journal of Mathematics, Vol. 13, pp. 179–191 (1961). https://doi.org/10.4153/CJM-1961-015-3
• http://www.prefield.com/algorithm/dp/lis_fast.html
• http://noshi91.hatenablog.com/entry/2018/02/03/204950

TODO

• longest Zig-Zag subsequence
  • https://github.com/spaghetti-source/algorithm/blob/master/dynamic_programming/longest_zigzag_subsequence.cc
• range longest increasing subsequence query
  • https://twitter.com/noshi91/status/1388201116148539393
  • https://judge.yosupo.jp/problem/static_range_lis_query

Submissons

https://judge.yosupo.jp/submission/99391

Verified with

• 動的計画法/最長増加部分列 (test/dynamic_programming/longest_increasing_subsequence.test.cpp)

Code

#ifndef EMTHRM_DYNAMIC_PROGRAMMING_LONGEST_INCREASING_SUBSEQUENCE_HPP_
#define EMTHRM_DYNAMIC_PROGRAMMING_LONGEST_INCREASING_SUBSEQUENCE_HPP_

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

namespace emthrm {

template <bool IS_STRICT = true, typename T>
std::vector<T> longest_increasing_subsequence(const std::vector<T>& a) {
  const T inf = std::numeric_limits<T>::max();
  const int n = a.size();
  std::vector<int> idx(n);
  std::vector<T> tmp(n, inf);
  for (int i = 0; i < n; ++i) {
    idx[i] = std::distance(
        tmp.begin(),
        IS_STRICT ? std::lower_bound(tmp.begin(), tmp.end(), a[i]) :
                    std::upper_bound(tmp.begin(), tmp.end(), a[i]));
    tmp[idx[i]] = a[i];
  }
  int res_size =
      std::distance(tmp.begin(), std::lower_bound(tmp.begin(), tmp.end(), inf));
  std::vector<T> res(res_size--);
  for (int i = n - 1; res_size >= 0 && i >= 0; --i) {
    if (idx[i] == res_size) res[res_size--] = a[i];
  }
  return res;
}

}  // namespace emthrm

#endif  // EMTHRM_DYNAMIC_PROGRAMMING_LONGEST_INCREASING_SUBSEQUENCE_HPP_

#line 1 "include/emthrm/dynamic_programming/longest_increasing_subsequence.hpp"



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

namespace emthrm {

template <bool IS_STRICT = true, typename T>
std::vector<T> longest_increasing_subsequence(const std::vector<T>& a) {
  const T inf = std::numeric_limits<T>::max();
  const int n = a.size();
  std::vector<int> idx(n);
  std::vector<T> tmp(n, inf);
  for (int i = 0; i < n; ++i) {
    idx[i] = std::distance(
        tmp.begin(),
        IS_STRICT ? std::lower_bound(tmp.begin(), tmp.end(), a[i]) :
                    std::upper_bound(tmp.begin(), tmp.end(), a[i]));
    tmp[idx[i]] = a[i];
  }
  int res_size =
      std::distance(tmp.begin(), std::lower_bound(tmp.begin(), tmp.end(), inf));
  std::vector<T> res(res_size--);
  for (int i = n - 1; res_size >= 0 && i >= 0; --i) {
    if (idx[i] == res_size) res[res_size--] = a[i];
  }
  return res;
}

}  // namespace emthrm

Back to top page