LIS(最長増加部分列) (dp/lis.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-10-06 03:54:40+09:00

なにこれ

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

関数

• LIS(v, strict)：配列 v の最長増加部分列の長さを返す．strict が true の場合は狭義単調，false の場合は広義単調の長さを返す．

計算量

v の要素数を $n$ とする．

• $O(n \log n)$

Verified with

• test/aoj_DPL_1_D.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T> int LIS(const vector<T> &v, bool strict = true) {
	vector<T> lis;
	if(strict) {
		for(T a : v) {
			auto itr = lower_bound(lis.begin(), lis.end(), a);
			if(itr == lis.end()) lis.emplace_back(a);
			else
				*itr = a;
		}
	}
	else {
		for(T a : v) {
			auto itr = upper_bound(lis.begin(), lis.end(), a);
			if(itr == lis.end()) lis.emplace_back(a);
			else
				*itr = a;
		}
	}
	return lis.size();
}

#line 2 "dp/lis.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T> int LIS(const vector<T> &v, bool strict = true) {
	vector<T> lis;
	if(strict) {
		for(T a : v) {
			auto itr = lower_bound(lis.begin(), lis.end(), a);
			if(itr == lis.end()) lis.emplace_back(a);
			else
				*itr = a;
		}
	}
	else {
		for(T a : v) {
			auto itr = upper_bound(lis.begin(), lis.end(), a);
			if(itr == lis.end()) lis.emplace_back(a);
			else
				*itr = a;
		}
	}
	return lis.size();
}

Back to top page