python - Python を使用して最長増加部分列を見つけるための反復ソリューション

Question

bisect を使用して最長増加サブシーケンスの反復ソリューションを実装しようとしています。私の実装は、ある時点で失敗しています。修正を手伝ってください。

実装：

from bisect import bisect

def lis_iterative(seq):
    buff = []
    for n in seq:
        i = bisect(buff, n)
        if i == len(buff):
            buff.append(n)
        else:
            buff[i] = n
    return buff

def main():
    seq = [43, 25, 6, 37, 27, 26, 7, 24, 457, 5, 22, 72]
    print lis_iterative(seq)

main()

期待される出力:

[6, 7, 24, 457]

生成された出力:

[5, 7, 22, 72]