Edited at

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


longest increasing subsequence

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

S = a1, a2 , , , an

の増加部分列 ( すべてのi, j (i < j)について ai < aj を満たす部分列 )

の中で長さが最大のものをいいます。

最長増加部分列の長さを求めるアルゴリズムpythonで実装すると、こうなります。

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