Longest Increasing Subsequence with Linear and Bisect (Binary) Search - http://research.variancia.com/unl-aligner/

longest_subsequence.py

def longest_subsequence_bisect(seq, mode='strictly', order='increasing',
                        key=None, index=False):
    """

    >>> longest_subsequence_bisect([1,2,3,4,5,6,7,2,2,2,2,2,5,1,7,8])

    Return the longest increasing subsequence of `seq`.

    Parameters
    ----------
    seq : sequence object
    Can be any sequence, like `str`, `list`, `numpy.array`.
    mode : {'strict', 'strictly', 'weak', 'weakly'}, optional
    If set to 'strict', the subsequence will contain unique elements.
    Using 'weak' an element can be repeated many times.
    Modes ending in -ly serve as a convenience to use with `order` parameter,
    because `longest_sequence(seq, 'weakly', 'increasing')` reads better.
    The default is 'strict'.
    order : {'increasing', 'decreasing'}, optional
    By default return the longest increasing subsequence, but it is possible
    to return the longest decreasing sequence as well.
    key : function, optional
    Specifies a function of one argument that is used to extract a comparison
    key from each list element (e.g., `str.lower`, `lambda x: x[0]`).
    The default value is `None` (compare the elements directly).
    index : bool, optional
    If set to `True`, return the indices of the subsequence, otherwise return
    the elements. Default is `False`.

    Returns
    -------
    elements : list, optional
    A `list` of elements of the longest subsequence.
    Returned by default and when `index` is set to `False`.
    indices : list, optional
    A `list` of indices pointing to elements in the longest subsequence.
    Returned when `index` is set to `True`.
    """
    bisect = bisect_left if mode.startswith('strict') else bisect_right

    # compute keys for comparison just once
    rank = seq if key is None else map(key, seq)
    if order == 'decreasing':
        rank = map(cmp_to_key(lambda x,y: 1 if x<y else 0 if x==y else -1), rank)
    rank = list(rank)

    if not rank: return []

    lastoflength = [0] # end position of subsequence with given length
    predecessor = [None] # penultimate element of l.i.s. ending at given position

    for i in range(1, len(seq)):
        # seq[i] can extend a subsequence that ends with a lesser (or equal) element
        j = bisect([rank[k] for k in lastoflength], rank[i])
        # update existing subsequence of length j or extend the longest
        try: lastoflength[j] = i
        except: lastoflength.append(i)
        # remember element before seq[i] in the subsequence
        predecessor.append(lastoflength[j-1] if j > 0 else None)
        
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([])
    []
    @see http://research.variancia.com/unl-aligner/
    '''
    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

The longest_subsequence_linear algorithm is taken from unl-aligner.