Iterative solution to finding Longest Increasing Subsequence using Python

Question

I am trying to implement an iterative solution for Longest Increasing Subsequence using bisect. My implementation is failing at some point. Help me fix it.

Implementation:

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()

Expected Output:

[6, 7, 24, 457]

Generated Output:

[5, 7, 22, 72]

Answer 1

Your current algorithm doesn't seem to make much sense, as noted in BrenBarn's comment. Here is what I came up with:

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