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]

This algorithm doesn't make sense to me. If you find a number bigger than the biggest, you stick it on the end, but if you find one smaller than the smallest, you just overwrite the first element, which can mean buff is no longer a subsequence (since you put a later element in at an earlier position). — BrenBarn
– BrenBarn, Commented Jan 2, 2014 at 22:52

Andrew Clark · Accepted Answer · 2014-01-02 23:25:13Z

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

Collectives™ on Stack Overflow

Iterative solution to finding Longest Increasing Subsequence using Python

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related