longest-increasing-subsequence(dp)
(kyopro/library/algorithm/LIS_dp.cpp)

• View this file on GitHub
• Last update: 2022-07-20 00:04:43+09:00



説明

最長増加部分列の長さを求める

使い方

関数
lis($n, A, f$)

引数

• $n$: 配列の長さ
• $A$: 配列
• $f$: 狭義かどうか

返り値

• 長さ

計算量

${\rm O}(n \log n)$

Verified with

• kyopro/test/LIS_dp_aoj.test.cpp

Code

/*
* @title longest-increasing-subsequence(dp)
* @docs kyopro/docs/LIS_dp.md
*/

//st が true の時、狭義単調増加
int lis(const int& n, const vector<int>& a, const bool& st) {
	vector<int> dp(n);
	fill(all(dp), INF);
	vector<int>::iterator ite;
	rep(i, n) {
		if (st)ite = lower_bound(all(dp), a[i]);
		else ite = upper_bound(all(dp), a[i]);
		if (ite != dp.end())*ite = a[i];
	}
	return distance(dp.begin(), lower_bound(all(dp), INF));
}

#line 1 "kyopro/library/algorithm/LIS_dp.cpp"
/*
* @title longest-increasing-subsequence(dp)
* @docs kyopro/docs/LIS_dp.md
*/

//st が true の時、狭義単調増加
int lis(const int& n, const vector<int>& a, const bool& st) {
	vector<int> dp(n);
	fill(all(dp), INF);
	vector<int>::iterator ite;
	rep(i, n) {
		if (st)ite = lower_bound(all(dp), a[i]);
		else ite = upper_bound(all(dp), a[i]);
		if (ite != dp.end())*ite = a[i];
	}
	return distance(dp.begin(), lower_bound(all(dp), INF));
}

Back to top page