例題

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_x

概要 : 配列 $A$ を与える。最長部分増加列の長さを求めろ。

コード

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int>a(n);
	for(int i=0;i<n;++i)cin>>a[i];
	const int inf = 1<<30;
	vector<int> LIS(n,inf);
	LIS[0]=a[0];
	for(int i=1;i<n;++i){
		const int &target = a[i];
		auto it = lower_bound(LIS.begin(),LIS.end(),target);
		*it = a[i];
	}

	int ans = lower_bound(LIS.begin(),LIS.end(),inf) - LIS.begin();
	cout << ans << endl;
}

実装内容

DPテーブルに増加部分列の長さをindexとしたときの最後の$A_i$の値を入れていく。

$\mathrm{DP}[0]$ は 自明に $A_0$ になる。

そこから $A_i$ を見ていき $\mathrm{DP}[0]$ から $\mathrm{DP}[n-1]$ までの値の中で $A_i$ より大きい値を見つけたらそのDPテーブルのindexに $A_i$ を入れる。

以上を繰り返す。

DPテーブルに inf 以外の値が入っている個数は最長部分増加列の長さになる。

<aside> 🚫

DPテーブルの値が最長部分増加列自体ではないことに注意

</aside>

解説