最長増加部分文字列(longest increasing subsequence)をpythonで

longest increasing subsequence

最長増加部分列とは、与えられた数列 S

$S = a_1, a_2 , , , a_n $

の増加部分列　（ すべての$i$, $j$ ($i$ < $j$)について $a_i$ < $a_j$ を満たす部分列 ）
の中で長さが最大のものをいいます。

以下、最長増加部分列の長さを求めるプログラムです。

from bisect import bisect_left


def lis(li):
    lis_li = [li[0]]
    for i in li:
        if i > lis_li[-1]:
            lis_li.append(i)
        else:
            lis_li[bisect_left(lis_li, i)] = i
    return lis_li