7K12 blog

猫でも分かるアルゴリズム解説

AOJ DPL_1_D Longest Increasing Subsequence

f:id:tkr987:20200731233117p:plain

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4726957

  • 最長増加部分列の計算量は O(N \log N)

f:id:tkr987:20200731234902p:plain

小さい数字に貪欲に更新することで部分列の長さが増加する可能性を増やす。二分探索したときendであれば、その数字を追加することで長さが1増える。更新するべきかどうか二分探索することで全体計算量が O(N \log N)になる。なお、lower_boundをupper_boundにすることで広義最長増加部分列の長さを得ることも出来る。