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を使う？
いやそれとも、さっきのやり方なんか参考にしない、全然違うやり方？
・・・
このへんであきらめて解説を読みすすめるか