りす
LISの長さをsegtreeを使って求めます。
問題
最長増加部分列 | 動的計画法 | Aizu Online Judge
問題概要
数列からもとの順番を保って要素を取り出して並べるとき、狭義の単調増加数列になっているものの長さの最大値を求める。
解き方
しばらくの間は広義のLIS(LDNS:LongestNonDecreasingSubsequence)を考えます。
末尾に要素を追加してLISを伸ばすとき、LISの全要素を知る必要はありません。LISの最後の要素と、追加したい要素が分かっていて
が成り立っていれば要素を追加でき、LISを伸ばせます。そこで、$lis_i$を次のように定義します。
もとの数列を$a=\{a_1, a_2, \ldots, a_n\}$とします。$lis_i$は$a_i$を必ず使うことにして、$a_1, a_2, \ldots, a_{i-1}$からうまく選んだときのLISの長さ*1です。この$lis$は次の漸化式で定まります。
- $lis_{i}=1$ (NOT exist $j$ s.t. $a_j\leq a_i,\ j<i$})
- $lis_{i}=\displaystyle\max_{a_j \le a_i,\ j<i}\ (lis_j)+1$ (otherwise)
最終的に求めたいのは$a$のLISの長さなので$\max(lis_i)\ (1\leq i\leq n)$です。各$lis_i$を計算する1つの方法は、$i$の小さい順に確定させていくことです。疑似コードで表すと次のようになります。
a=input_array() lis=array.new(n) for i in 1 to n ma=0 for j in 1 to i-1 if a[j]<=a[i] ma=max(ma, lis[j]) end end lis[i]=ma+1 end
二重ループなので計算量は$\mathcal{O}(n^2)$*2です。$[1, i)$での$lis$の最大値を求める部分はsegtreeが使えますが、もし$lis=lis_j$で最大値になるとしてその$j$に対して$a_j\leq a_i$となっているとは限りません。
そこで$a_i$の小さい順に確定させていくことを考えます(簡単のため各$a_i$はdistinctだとします)。この場合$lis_i$を計算する時点では、$a_i<a_j$なる$j$に対して$lis_j$は未計算なので、$lis$の初期値を負の数にでもしておけば先程の問題は解消されます。*3
$\{a_i\}$に同じ要素が複数含まれる場合はLISの種類に応じて、同じ値の中での優先度を次のようにします。
- 広義単調増加なら$i$の小さい順
- 狭義単調増加なら$i$の大きい順
広義のLISなら$i<j,\ a_i=a_j$なる$i, j$に対して、$lis_j=lis_i+1$とすることは許されますが狭義ならダメというあれです。
解答例
$lis$の初期値を0にしておくことで、$a_j<a_i,\ j<i$なる$j$が存在しない場合でも$lis_i=\max(lis_j)+1=0+1=1$となります。
LongestIncreasingSubsequence(strictly increasing)
おわりに
構造体の名前をDataにしようとしたら怒られました。
LISの長さのことをいちいち“LISの長さ”って言うのめんどうですね。
参考
http://blog.manujith.me/2015/08/explained-finding-longest-increasing.html