Longest Common Sub Sequence (LCS) Linear

longest_subsequence_linear.py

def longest_subsequence_linear(seq, keyfn=lambda value: value):
    ''' Longest Increasing Subsequence
    >>> seq = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
    >>> lis(seq)
    [0, 2, 6, 9, 11, 15]
    >>> lis([])
    []
    '''
    if not seq: return seq

    # tail[k] stores the position i of the smallest value seq[i] such that 
    # there is an increasing subsequence of length (k+1) ending at seq[i]
    tail = []
    # prev[k] stores the position i of the rightmost seq[i] such that
    # seq[i] < seq[k]
    prev = []
    for i in range(len(seq)):
        # find the rightmost tail[k] such that seq[tail[k]] < seq[i]
        # TODO: bisect tail instead of linear scan
        for k in range(len(tail)-1, -1, -1):
            if keyfn(seq[tail[k]]) < keyfn(seq[i]):
                if len(tail) == k+1:
                    tail.append(i)
                elif keyfn(seq[tail[k+1]]) > keyfn(seq[i]):
                    tail[k+1] = i
                prev.append(tail[k])                    
                break
        else:
            tail.append(i)
            prev.append(None)

    i = tail[-1]
    subseq = [seq[i]]
    while prev[i] is not None:
        i = prev[i]
        subseq.append(seq[i])
    subseq.reverse()
    return subseq

Longest Common Sub Sequence (LCS) Bisect