DPL_1_D: Longest Increasing Subsequence (続き2)

このへんであきらめて解説を読みすすめるか

最初の考え方とは全然違うアプローチだった

L[i]を長さがi+1であるような増加部分列の最後の要素の最小値とする配列

なんだかややこしい
Lの最後の要素を更新していくっていうやり方じゃないんだな
読んでみても実はあんまりわかってない

適当に数字を並べて試してみよう
[16 47 83 42 17 13 54]くらいでどうだ

まず16を取ってくる
長さ1の増加部分列[16]が作れて最後の要素は16
L[0]=16、L=[16]

47を取ってくる
長さ2の[16, 47]っていう増加部分列が作れるのでL[1]=47
L[0]は変わらない → L=[16, 47]

次
[16, 47, 83]っていう増加部分列が作れてL[2]=83
L[0]、L[1]は変わらない → L=[16, 47, 83]

このへんまでは何でもないんだけどここで42を取ってきたらどうなる
[16, 42]っていう増加部分列が作れるのでL[1]=42
L[0]、L[2]は変わらない → L=[16, 47, 83]

[16, 42, 83]っていう部分列は作れないけど、それでいいってことか
それがなんとなくダメだと思って考えるのやめてた感じだな
部分列は最大の要素だけわかってればそれ以外はどうでもいいわけだし
常にn個めまでの最善を尽くしてますっていう状態が残ってれば

頭の中ではできてるけどどういう条件で探してるのかピンときてなかったりする
更新されるのは必ず1か所なのかな
更新されない場合とか2か所以上更新されるとかないの
もうちょっと続ける

17を取ってきて[16, 17]でL[1]=17 L=[16, 17, 83]
13を取ってきて[13]でL[0]=13 ほかはそのまま L=[13, 17, 83]

そろそろわかってもいいんじゃネーノ
どこを置き換えることになるんだ
もう一度並べなおす

  : []
16: [16]
47: [16, 47]
83: [16, 47, 83]
42: [16, 42, 83]
17: [16, 17, 83]
13: [13, 17, 83]

持ってきた数がnだとすると
a) Lの末尾の要素よりもnのほうが大きければLにnを追加
b) そうでなければL[k-1] < n <= L[k]となるようなkを探してL[k] = nとする
ってことをしているように見える
まだ全部の場合を網羅できてるかどうかはわからないけど

a)はまあそれでいいとしてb)はどういうことかな
[16, 42, 83]で17を持ってきたとき、
長さ1の増加部分列[16]は更新することはできない
長さ2の増加部分列[16, 42]は[16, 17]に更新できる
長さ3以上の増加部分列[16, 42, ...]は[16, 17, ...]になるだけで末尾は変わらない
そういうことか
わかった気がするぞ

最初の要素は無条件に突っ込んでしまうか

わざわざ「L[i]を長さがi+1であるような増加部分列の」としてるのは
どうしてかな

じゃあ書くか
二分探索にする前に線形探索で書いてみよう
この場合は一番左に0があったほうがやりやすそう

def LIS(n, a):
    l = [-1, a[0]]
    for e in a[1:]:
        if l[-1] < e:
            l.append(e)
        else:
            for k in range(1, len(l)):
                if l[k - 1] < e <= l[k]:
                    l[k] = e
                    break
    return len(l) - 1

WAなしでTLE
今日はここまで