po

りす

LISの長さをsegtreeを使って求めます。

問題

最長増加部分列 | 動的計画法 | Aizu Online Judge

問題概要

数列からもとの順番を保って要素を取り出して並べるとき、狭義の単調増加数列になっているものの長さの最大値を求める。

解き方

しばらくの間は広義のLIS(LDNS:LongestNonDecreasingSubsequence)を考えます。

末尾に要素を追加してLISを伸ばすとき、LISの全要素を知る必要はありません。LISの最後の要素と、追加したい要素が分かっていて

LISの最後の要素$\leq$追加したい要素

が成り立っていれば要素を追加でき、LISを伸ばせます。そこで、$lis_i$を次のように定義します。

$lis_i=$もとの数列の$i$番目の要素が最後の要素になっているLISの長さ

もとの数列を$a=\{a_1, a_2, \ldots, a_n\}$とします。$lis_i$は$a_i$を必ず使うことにして、$a_1, a_2, \ldots, a_{i-1}$からうまく選んだときのLISの長さ*1です。この$lis$は次の漸化式で定まります。

$$ \begin{align*} &lis_{i}=1 &(\text{NOT exist $j$ s.t. $a_j\leq a_i,\ j<i$})\\ &lis_{i}=\max_{a_j\leq a_i,\ j<i} (lis_j)+1 &(\text{otherwise}) \end{align*} $$

最終的に求めたいのは$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の長さ”って言うのめんどうですね。

参考

ManZzup'z TutZ: Explained: Finding the Longest Increasing Subsequence using Segment Tree

*1:必ずしも$a_1, a_2, \ldots, a_i$のLISの長さと同じではありません。

*2:この$O$かっこいいですね。

*3:$i$を$a$の$i$番目に小さい要素のindexとすると、$[1, i)$での$lis$の最大値$lis_j$を与える$j$に対して$a_j\leq a_i$です。ただし、$lis_j<0$のときは漸化式の第1式の状況です。