最長増加部分列長とは？
(列)ある配列があって、
(部分列)その部分列(順番保ったまま幾つかの要素を取り出したもの、連続じゃなくてOK)のうち、
(増加部分列)要素が昇順になっているもののうち、
(最長増加部分列)最長のものの、
(最長増加部分列長)配列長さ。
例:
配列 [8, 2, 7, 4, 5, 9, 1, 6, 3]
=> [2, 4, 5, 9]( or [2, 4, 5, 6]) の配列長4が最大
求め方
配列長nの最長部分列を作ったときの最後の要素の最小値を保持しながら一つずつ要素を見ていくことで求めることができます。
多分この説明だけで分かる人は天才なので、以下に具体的な計算を示します。
配列 [8, 2, 7, 4, 5, 9, 1, 6, 3]
1つ目の要素を取り出す[8, 2, 7, 4, 5, 9, 1, 6, 3]
| 配列長さ | 1 | 2... |
|---|---|---|
| 最後の要素の最小値 | 8 | (無理) |
2つ目の要素を取り出す[8, 2, 7, 4, 5, 9, 1, 6, 3]
| 配列長さ | 1 | 2... |
|---|---|---|
| 最後の要素の最小値 | 2 | (無理) |
3つ目の要素を取り出す[8, 2, 7, 4, 5, 9, 1, 6, 3]
| 配列長さ | 1 | 2 | 3 |
|---|---|---|---|
| 最後の要素の最小値 | 2 | 7 | (無理) |
4つ目の要素を取り出す[8, 2, 7, 4, 5, 9, 1, 6, 3]
| 配列長さ | 1 | 2 | 3... |
|---|---|---|---|
| 最後の要素の最小値 | 2 | 4 | (無理) |
5つ目の要素を取り出す[8, 2, 7, 4, 5, 9, 1, 6, 3]
| 配列長さ | 1 | 2 | 3 | 4... |
|---|---|---|---|---|
| 最後の要素の最小値 | 2 | 4 | 5 | (無理) |
6つ目の要素を取り出す[8, 2, 7, 4, 5, 9, 1, 6, 3]
| 配列長さ | 1 | 2 | 3 | 4 | 5... |
|---|---|---|---|---|---|
| 最後の要素の最小値 | 2 | 4 | 5 | 9 | (無理) |
7つ目の要素を取り出す[8, 2, 7, 4, 5, 9, 1, 6, 3]
| 配列長さ | 1 | 2 | 3 | 4 | 5... |
|---|---|---|---|---|---|
| 最後の要素の最小値 | 1 | 4 | 5 | 9 | (無理) |
8つ目の要素を取り出す[8, 2, 7, 4, 5, 9, 1, 6, 3]
| 配列長さ | 1 | 2 | 3 | 4 | 5... |
|---|---|---|---|---|---|
| 最後の要素の最小値 | 1 | 4 | 5 | 6 | (無理) |
9つ目の要素を取り出す[8, 2, 7, 4, 5, 9, 1, 6,3]
| 配列長さ | 1 | 2 | 3 | 4 | 5... |
|---|---|---|---|---|---|
| 最後の要素の最小値 | 1 | 3 | 5 | 6 | (無理) |
上記のような手順で最長増加部分列長を4と求めることができました。
※当然ですが、上記情報からだけでは、
最長増加部分列の具体的な要素の内容については求めることができません。
(=> [1,3,5,6] という数字の並びは、部分列ではないです)
最後の要素の最小値 の配列の要素を上書きしたり、後ろに追加したりという作業を繰り返すことで、最長増加部分列長を求めることができるのですが、
もう少し踏み込んで、具体的にどのようにその処理を行うかを次に記します。
処理の詳細について
-
要素の追加について
取り出した要素が、「最後の要素の最小値の配列」の最後の要素よりも大きかった場合には、配列の最後に取り出した要素を追加します。 -
要素の上書きについて
取り出した要素が、「最後の要素の最小値の配列」の最後の要素よりも大きくは無い場合、
「最後の要素の最小値の配列」のうち、取り出した要素より大きいものの最小の要素を取り出した要素で上書きします。
ということで、要素を取り出したあとは、「最後の要素の最小値 の配列」と比較したりして、適宜いいところに上書き・挿入をしてきます。
上記の要素の挿入箇所の探索には二分探索を用いることができます。
なぜなら「最後の要素の最小値 の配列」が常にソート済み配列になるからです。
これは挿入・追加の手順を考えれば明らかで、
最大なら最後に挿入 = ソート済みを崩さない
最大じゃないなら書き換え = 書き換える前後の要素の間の値に書き換えるだけなのでソート済みを崩さない。
またRubyはArray#bsearch_indexというバカでも二分探索できるメソッドが存在するので、これを使えば上記の処理は非常にかんたんに実装ができます。
そんな感じで、最長増加部分列長を求めるメソッドを作りました。
実装例
class Array
def lis
# b_ary = 「`最後の要素の最小値` の配列」です
# 1つ目の要素は見るまでもなく要素1つ目までを使ったときの配列長1の最小値になっています。
b_ary = [self[0]]
self[1..-1].each do |v|
# 「`最後の要素の最小値` の配列」 から
# 取り出した要素以上の最小値のindexを求めます
index = b_ary.bsearch_index { |x| x >= v }
if index
# そんなindexがあれば上書きをします。
b_ary[index] = v
else
# そんなindexがない=取り出した要素は「`最後の要素の最小値` の配列」の最後の要素より大きい
# このときは、最後に要素を挿入します
b_ary << v
end
end
return b_ary.size
end
end
ちなみに 広義単調増加/狭義単調増加、広義単調減少/狭義単調減少の4パターンがありますが、
b_ary.bsearch_index { |x| x >= v } のブロックの中の >= を適宜差し替えるだけで大丈夫です。
(広義と狭義の違いは、等号を含めるかどうかです)
最後に、最長増加部分列長の求め方知ってればすぐに解ける問題(ネタバレ)をおいてきます。是非挑戦してみてください。
https://atcoder.jp/contests/abc134/tasks/abc134_e
https://github.com/k-karen/ruby-samples/blob/master/lis/abc134e.rb (解答例)