DPL_1_D: Longest Increasing Subsequence (続き)
わからなかったので解説を見る
ふたつ考え方が載っていて、ひとつめは2乗のオーダで時間がかかるので使えない
んだけどまずこっちを理解しよう
L[i]
をA[i]
からA[i]
までの要素を使いA[i]
を最後に選んだ時のLISの長さとする配列
なるほど「A[i]
を最後に選んだ時の」を考えるわけか
その代わりL[k]
を求めるにはk-1
までのLの最大値をもとめないといけないので
オーダが2乗になってしまう
こんなロジック
def LIS(n, a):
l = [0] * (n + 1)
for i in range(1, n + 1):
for j in range(0, i):
if a[j] < a[i]:
l[i] = max(l[i], l[j])
l[i] += 1
return l
a
やl
の本体はa[1]
やl[1]
から始まるけど
a[0]
やl[0]
も初期値として使われる
配列は0オリジンなのに添字は1からっていう場合もこういうのだとうまくいった感があるな
なおテキストではひとつ前の要素の位置をP
に覚えてるけど
これはLISの長さを出すためには使わないから無視した
ジャッジにかけると想定通りTLE
WAは出ていないから大丈夫
ここでいったん自分で考えてみよう
これでは遅すぎるからと二分探索を組み合わせてオーダをnlognにするってことだろう
l
がソートされてればごく普通に二分探索でいいわけだけど
ここではそうなっていない
増えていくけど減ることもある
l
はl
で覚えておくとして、最大値も覚えておけばいいのかな?
いやそれでもだめかな
ただの最大値じゃなくてa[j] < a[i]
を満たすj
における最大値だもんなほしいのは
まんなかを決めたとき、求める要素が右にあるか左にあるか、
どうやって判断するのかってことだよな
少なくともl
を見ただけではわかりそうな気がしないから何かほかを使うんだろうな
もしかしてP
を使う?
いやそれとも、さっきのやり方なんか参考にしない、全然違うやり方?
・・・
このへんであきらめて解説を読みすすめるか