LIS - かに

LIS

数列の（連続とは限らない）部分列で、単調増加であるもののうち長さが最大のものを求める。

計算量：$ O(NlogN)

単純な動的計画法だと$ O(N^2)

in-place DPで二分探索を用いて更新すると$ O(NlogN)

区間maxのセグメント木を更新していく方法でも$ O(NlogN)

狭義単調増加の部分列の長さを求める場合、

$ seg[0\rbrack=0で初期化し、$ seg[A_i\rbrack = max([0,A_i)) + 1

参照区間を閉区間$ max([0,A_i\rbrack)にすれば広義単調増加になる。

+1の部分を変えれば長さではなく各項に対応付けされた価値の最大化も可能。