Longest Increasing Subsequence (LIS)
(library/misc/lis.hpp)

• View this file on GitHub
• Last update: 2025-12-21 19:31:20+09:00
• Include: #include "library/misc/lis.hpp"

最長増加部分列（LIS)。

• vector<int> lis(const vector<T>& A, const bool strict = true)

A の LIS を構成する index の 1 つを返す。

計算量は $O(n \log n)$。

Verified with

• tests/misc/lis/libchecker.test.cpp

Code

#pragma once

#include <algorithm>
#include <ranges>
#include <vector>
using namespace std;

namespace asalib::misc {
  template<class T>
  vector<int> lis(const vector<T>& a, const bool strict = true) {
    vector<T> dp(0);
    vector<int> idx(a.size());
    for (int i = 0; i < ranges::ssize(a); ++i) {
      decltype(ranges::begin(dp)) it;
      if (strict)
        it = ranges::lower_bound(dp, a[i]);
      else
        it = ranges::upper_bound(dp, a[i]);
      if (it == ranges::end(dp)) {
        idx[i] = ranges::ssize(dp);
        dp.push_back(a[i]);
      }
      else {
        idx[i] = ranges::distance(ranges::begin(dp), it);
        *it = a[i];
      }
    }
    vector<int> res(dp.size());
    int j = ranges::ssize(dp) - 1;
    for (int i = ranges::ssize(a) - 1; i >= 0; --i) {
      if (idx[i] == j) {
        res[j] = i, --j;
      }
    }
    return res;
  }
}  // namespace asalib::misc

#line 2 "library/misc/lis.hpp"

#include <algorithm>
#include <ranges>
#include <vector>
using namespace std;

namespace asalib::misc {
  template<class T>
  vector<int> lis(const vector<T>& a, const bool strict = true) {
    vector<T> dp(0);
    vector<int> idx(a.size());
    for (int i = 0; i < ranges::ssize(a); ++i) {
      decltype(ranges::begin(dp)) it;
      if (strict)
        it = ranges::lower_bound(dp, a[i]);
      else
        it = ranges::upper_bound(dp, a[i]);
      if (it == ranges::end(dp)) {
        idx[i] = ranges::ssize(dp);
        dp.push_back(a[i]);
      }
      else {
        idx[i] = ranges::distance(ranges::begin(dp), it);
        *it = a[i];
      }
    }
    vector<int> res(dp.size());
    int j = ranges::ssize(dp) - 1;
    for (int i = ranges::ssize(a) - 1; i >= 0; --i) {
      if (idx[i] == j) {
        res[j] = i, --j;
      }
    }
    return res;
  }
}  // namespace asalib::misc

Back to top page