python - 使用 Python 查找最长递增子序列的迭代解决方案

Question

我正在尝试使用二分法实现最长递增子序列的迭代解决方案。我的实现有时会失败。帮我修一下。

实现:

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]

Answer 1

如 BrenBarn 的评论所述，您当前的算法似乎没有多大意义。这是我想出的:

def lis_iterative(seq):
    n = len(seq)
    dp = [(0, -1)]*n
    # dp contains (best, idx) tuples, where best is the length of the longest
    # increasing sequence starting from that element, and idx is the index of the
    # next element in that sequence
    for i in range(n-1, -1, -1):
        best = 0
        idx = -1
        for j in range(i+1, n):
            if seq[i] < seq[j] and dp[j][0] + 1 > best:
                best = dp[j][0] + 1
                idx = j
        dp[i] = (best, idx)

    # find longest increasing sequence from dp, then follow idx chain for result
    result = []
    idx = max(range(n), key=lambda i: dp[i][0])
    while idx != -1:
        result.append(seq[idx])
        _, idx = dp[idx]
    return result