RE：ゼロから始めるLIS問題 - ミケ猫の小部屋

最長部分増加列（LIS）問題は序列 $a_1 a_2 a_3 \dots a_n$ の単調増加の部分列の中で一番長い部分列の長さを求める問題である。最近ARC 104の問題

を見ていたらLIS問題を振り替えようと思います。

貪欲アルゴリズム

配列 $dp[i$ ]があるとする。dp[i]は長さがiの部分増加列の最後の要素の最小値を表す。例えば列 $1 2 3 4 5$ 全体に対して、長さが4になる部分増加列は $1 2 3 4$ などの五通りある。その中で最後の要素の最小値は４なのでdp[4]=4になる。

このアルゴリズムは配列の要素ごとに以下のプロセスを繰り返す。

このアルゴリズムは簡単で、ツリー上のLIS問題にも適用する。

また配列dpを用意して、今回は $dp_i$ を「iが最後となる部分増加列の長さ」にする。BITを使って効率よく $dp_1$ から $dp_k$ までの最大値を探す。アルゴリズムは元の配列要素ごとに以下のプロセスを繰り返す。

この方法が成立する前提は全ての要素更新は要素を大きくすること。そして区間最大値は全部初めから計算したもの。この方法は貪欲アルゴリズムより複雑だけど、LISだけでなくより複雑な制約を扱える。例えばこのLaIS問題。