Longest Increasing Subsequence

sequence/lis.hpp · GitHub で見る

共通ページ

列から要素を順序通りに選び、値が増加する部分列の最大長と、そのような部分列の 1 つを求めます。元の列で連続している必要はありません。数値以外の要素や独自の比較にも対応します。

#include "lib/sequence/lis.hpp"

std::vector<int> a{3, 1, 2, 2, 4};
int length = lis_length(a);       // 3
auto indices = lis(a);            // 1, 3, 4
auto lengths = lis_lengths(a);    // 1, 1, 2, 2, 3

std::vector<int> values;
for (int i : indices) values.push_back(a[i]); // 1, 2, 4

int weak_length = lis_length<false>(a); // 4
auto weak_indices = lis<false>(a);     // 1, 2, 3, 4

既定は狭義増加 \(a_{i_0}<a_{i_1}<\cdots\) です。<false> を指定すると、等しい値を続けて選べる広義増加 \(a_{i_0}\le a_{i_1}\le\cdots\) になります。上の例で、狭義増加では 2 を 1 個、広義増加では 2 個選べます。

lis が返すのは値そのものではなく、元の列の 0 始まりの添字列 です。添字は昇順で、a[indices[i]] として値を取り出します。答えが複数ある場合は、そのうち 1 つを返します。

lis_lengths(a)[i] は、位置 i を必ず最後に選ぶ部分列 の最大長です。例えば [1,2,3,0] に対しては [1,2,3,1] を返します。位置 i までの列全体での最大長が必要なら、この配列の先頭から最大値を累積してください。

操作	内容・返り値	計算量
lis_length(a,compare = std::less<>{})	狭義増加部分列の最大長を int で返す	\(O(n\log n)\)
lis(a,compare = std::less<>{})	狭義増加部分列の添字を vector<int> で返す	\(O(n\log n)\)
lis_lengths(a,compare = std::less<>{})	各位置を終点とする狭義増加部分列の長さを vector<int> で返す	\(O(n\log n)\)
lis_length<false>(a,compare) / lis<false>(a,compare) / lis_lengths<false>(a,compare)	広義増加で同じ計算を行う。比較関数は省略可	\(O(n\log n)\)

a は const でサイズ取得とランダムアクセスができる範囲を渡します。vector・array・C 配列・span・deque・string_view などに対応します。長さは INT_MAX 以下としてください。空の列では長さ 0、添字列と各位置の長さは空配列になります。元の列は変更しません。

比較関数は厳密弱順序を定めるものを使います。狭義の場合は compare(x,y)、広義の場合は !compare(y,x) を満たす順に要素を選びます。例えば std::greater<>{} を渡すと、減少部分列を求められます。

#include "lib/sequence/lis.hpp"

std::vector<int> a{5, 3, 4, 2, 1};
auto decreasing = lis(a, std::greater<>{}); // 値は 5, 4, 2, 1

struct Item { int key; int id; };
std::vector<Item> items{Item{3, 0}, Item{1, 1}, Item{2, 2}};
auto indices = lis(items, [](const Item &x, const Item &y) {
	return x.key < y.key;
});

小さい自明にコピー可能な要素は、末尾候補の値を連続配列に保持します。それ以外は元の列の添字を保持するため、要素がコピーできなくても比較できれば使えます。番兵や値の加減算を使わず、整数型の上限・下限もそのまま扱えます。

比較・小さい要素のコピーを \(O(1)\) として、時間は全て \(O(n\log n)\) です。答えの長さを \(L\) とすると、lis_length の追加空間は \(O(L)\)、lis・lis_lengths の追加空間は \(O(n)\) です。

依存ライブラリ

• 単調な述語の境界探索

検証コード

• test/lis.test.cpp

コード

#ifndef LIS_HPP
#define LIS_HPP

#include "../components/binary_search.hpp"
#include <cassert>
#include <cstddef>
#include <functional>
#include <limits>
#include <ranges>
#include <type_traits>
#include <utility>
#include <vector>

namespace lis_detail {
template<class Range>
concept Sequence = std::ranges::random_access_range<const Range> && std::ranges::sized_range<const Range>;

template<bool Strict, bool Record, Sequence Range, class Compare>
int scan(const Range &a, Compare &compare, int *lengths) {
	assert(std::ranges::size(a) <= std::size_t(std::numeric_limits<int>::max()));
	int n = static_cast<int>(std::ranges::size(a));
	using T = std::ranges::range_value_t<const Range>;
	constexpr bool cached = std::is_trivially_copyable_v<T> && sizeof(T) <= 16 &&
		std::is_copy_constructible_v<T> && std::is_copy_assignable_v<T> && !std::is_same_v<T, bool>;
	using Stored = std::conditional_t<cached, T, int>;
	std::vector<Stored> tails;
	if constexpr (Record) tails.reserve(n);
	auto first = std::ranges::begin(a);
	auto tail = [&](int p) -> decltype(auto) {
		if constexpr (cached) return (tails[p]);
		else return first[tails[p]];
	};
	auto before = [&](const auto &x, const auto &y) {
		if constexpr (Strict) return bool(compare(x, y));
		else return !compare(y, x);
	};
	for (int i = 0; i < n; ++i) {
		auto &&value = first[i];
		int p = static_cast<int>(tails.size());
		if (p && !before(tail(p - 1), value)) {
			if constexpr (cached) {
				auto *begin = tails.data(), *it = begin;
				for (unsigned width = p; width > 1;) {
					unsigned half = width / 2;
					width -= half;
					it += unsigned(before(it[half - 1], value)) * half;
				}
				p = int(it - begin);
			} else p = binary_search_detail::partition_point(p - 1, [&](int k) { return before(tail(k), value); });
		}
		if constexpr (cached) {
			if (p == static_cast<int>(tails.size())) tails.emplace_back(value);
			else tails[p] = value;
		} else {
			if (p == static_cast<int>(tails.size())) tails.push_back(i);
			else tails[p] = i;
		}
		if constexpr (Record) lengths[i] = p + 1;
	}
	return static_cast<int>(tails.size());
}
}

template<bool Strict = true, lis_detail::Sequence Range, class Compare = std::less<>>
int lis_length(const Range &a, Compare compare = {}) {
	return lis_detail::scan<Strict, false>(a, compare, nullptr);
}

template<bool Strict = true, lis_detail::Sequence Range, class Compare = std::less<>>
std::vector<int> lis_lengths(const Range &a, Compare compare = {}) {
	assert(std::ranges::size(a) <= std::size_t(std::numeric_limits<int>::max()));
	std::vector<int> lengths(std::ranges::size(a));
	lis_detail::scan<Strict, true>(a, compare, lengths.data());
	return lengths;
}

template<bool Strict = true, lis_detail::Sequence Range, class Compare = std::less<>>
std::vector<int> lis(const Range &a, Compare compare = {}) {
	assert(std::ranges::size(a) <= std::size_t(std::numeric_limits<int>::max()));
	std::vector<int> lengths(std::ranges::size(a));
	int remaining = lis_detail::scan<Strict, true>(a, compare, lengths.data());
	std::vector<int> result(remaining);
	for (int i = static_cast<int>(lengths.size()); remaining && i--;) {
		if (lengths[i] == remaining) result[--remaining] = i;
	}
	return result;
}

#endif

Back to top page