DPL_1_D
問題
考察
解法1
$ O(N^{2})
dp[i]$ := a_iで終わる時の最長部分増加列の長さとする
前から順に $ a_i を見ていく
$ j<iで$ a_i より小さい $ a_jが存在する場合、a[j] に+1した値を a[i] に入れる
ない場合は、今見ている$ a_iだけの文字列になるので、$ a_iに1を入れる
前から順に$ a_iを見るためのループと、各$ a_iについて「$ j<iで$ a_i より小さい $ a_jが存在するか」を探索するループが必要になるので、2重ループになる
つまり、計算量が $ O(N^2)
解法2
$ O(Nlog_2 N)
dp[i] := 長さ $ i の増加部分列のうち、末尾の要素の最小値
j < iの時は必ず dp[j] < dp[i] が成り立つ(単調増加)
各 $ a_iに対し、今見ている値 ( $ a_i )より小さいやつがdpの中にいるか探索する( $ a_j < a_i となるような要素が存在する。そのインデックスを$ i とする)
その右隣 ( i+1 )に今入っている値( dp[i+1])を、今見ている値 ($ a_i)で更新可能かどうか確認する
今見ている値の方が小さければ更新
最終的に、INF以外の値の要素の長さが答え
前から順に$ a_iを見るためのループがあり、「今見ている値より小さいやつがdpの中にいるか探索する」部分で二分探索を使う そのため、計算量が $ O(Nlog_2 N)
実装
シミュレーション
解法1
https://gyazo.com/4cc7520e9831d909aba575f47becefd3
解法2
https://gyazo.com/7b9015bf61922e48eae4c2eb84343f1f
処理の流れ
実装
計算量は
$ O(N\log_2 N)
実装上の注意
所感
参考