d_tutuz https://blog.hatena.ne.jp/d_tutuz/ 数学/競プロメモ https://tutuz.hateblo.jp/ LIS LISとはLongest Increase Subsequence の略で最長増加部分列と呼ばれる問題です。増加部分列とはすべての i < j で a_i < a_j となっている部分列のことです。 簡単な例を見てみます。 a_n = {1,3,5,2,4,6} という数列 a_n を考えます。 この時の最長増加部分列の長さは 4 (1,3,4,6),(1,2,4,6) です。 この問題はDPで O(N logN) で解けます。 考え方は、同じ長さの増加部分列であれば最終要素が小さいほうがその後に有利です。例えば長さ4の2つの増加部分列があるとして、b_n={100,200,300,4… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftutuz.hateblo.jp%2Fentry%2F2018%2F06%2F18%2F214827" title="LISとは - 数学/競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-06-18 21:48:27 rich https://tutuz.hateblo.jp/entry/2018/06/18/214827 1.0 100%