最長増加部分列

目次

• 最長増加部分列とは
• アルゴリズム

最長増加部分列とは？

与えられるデータの配列をaとする。
かつ を満たす最長の部分列のこと。

アルゴリズム

最長増加部分列の個数を求めるアルゴリズムを説明する。
漸化式の作り方は2種類ある。

1. dp[i] := を最後の要素とする増加部分列の最大の長さ。
2. dp[i] := i+1の部分列の最後の要素となる最小の値。

1の場合のソースは以下となる。

int
getLIS()
{
	int dp[MAX_P];
	int res = 0;
	for (int i=0; i<P; ++i) {
		dp[i] = 1;
		for (int j=0; j<i; ++j) {
			if (a[j] < a[i]) {
				dp[i] = max(dp[i],dp[j]+1);
			}
		}
		res = max(res,dp[i]);
	}
	return res;
}

このアルゴリズムの計算量はとなる。

2の場合のソースは以下となる。

int
getLIS()
{
	int dp[MAX_P];
	fill(dp, dp + P, INF);
	int res = 1;
	for (int j=0; j<P; ++j) {
		for (int i=0; i<=j; ++i) {
			if (i == 0 || dp[i-1] < a[j]) {
				dp[i] = min(dp[i],a[j]);
				res = max(res,i+1);
			}
		}
	}
	return res;
}

2の場合の配列dpは単調増加である。長さが大きいのに、最後の要素の値が小さいのは矛盾だからである。
よって、二分探索を用いることで配列dpを埋めることができる。

long
getLIS()
{
	int dp[MAX_P];
	fill(dp, dp + P, INF);
	for (int i=0; i<P; ++i) {
		*lower_bound(dp, dp+P, a[i]) = a[i];
	}
	return lower_bound(dp, dp+P, INF) - dp;
}

lower_boundは三つ目の引数で指定した値以上の最初の要素を返す。