DPL_1_D: Longest Increasing Subsequence

最長増加部分列を求める

ヒントの絵の意味が分からないなあ
アイコンは1次元の動的計画法と二分探索
そうしてみるとヒントの絵も二分探索か

最長共通部分列ってのやったけどあれと似てるかなあ
ちょっと違うかなあ
あれは2次元の表作ったけど今回は１次元でいいみたいだし

1次元っていうと
n個めの数までの最長増加部分列の長さかなにか覚えておけば
n+1個めまでの最長増加部分列も出せるってこと？
なんかあんまりそんな気がしないんだけど
長さだけ覚えておくのではすくなくともダメだよな

再帰＋分割統治で考えるとすると・・・？

n-1個めまでで部分列の長さがlだったとして、

部分列の最後尾の数よりもn個めの数のほうが大きいときは
n個めまでだと部分列の長さがl+1になる
ちょっと嘘っぽいか
n個めまでしか見なければ確かにそうでも
その先まで見ると最適ではないことがあるし
そこが難しさの根っこな気がする

そうじゃないときは
そこからあらためて部分列を始めたほうが長くなるかもしれないし
そうじゃないかもしれない

複数の可能性があるから複数覚えておくのか？
今までにはないパターンだな
ちょっとほかの作戦を考えてからにしよう

後ろから見ていくやり方は使えるかな？
ダメっぽいな

n-1個めまでの部分列の長さを覚えておくんじゃなくて
何かほかのものを覚えておくとよかったりするかな？
n番目の要素からの部分列の長さを覚えておくってのはどうかな
だめか
最後尾の数の大きさで表を作って、部分列の長さを覚えるようにしたら？