LIS
Longest Increasing Subsequenceの略。
最長増加部分列のこと。最長の、増加している、部分列のこと。つまり
配列を$ Aとしたとき、 $ i<j かつ $ A_i<A_j を満たす最長の部分列のこと
連続していない部分列でもいいです。つまり、
{1,5,2,9,3,1,4,7,5,2,6,8,7,1,8,3,9,5,10} なら {1,2,3,4,5,6,7,8,9,10} になります。
LISの求め方
DPをする。 dp[i] // 長さがiの部分列を作る時の、右端の最小値とする。
よく考えると、DPの配列内の値、つまり右端の最小値は右に行けば行く（作る部分列が長くなる）ほど大きくなっているはずなのがわかります。
なのでDP配列内で二分探索ができて、
それぞれの文字をどの部分列の右端に追加するのか？→lower_boundで探す
そこに追加したとき今よりも良くなるのか？→min(1つ隣の値、今のに右端をくっつけたやつ)する
みたいなことをすればいいと思う（？）。
https://gyazo.com/d5f73db965559f63134fd7f6be56b7bc