Source code online books for professionals by professionals

Listing 8-7.  Longest Increasing Subsequence
from bisect import bisect
 
def lis(seq):                                   # Longest increasing subseq.
    end = []                                    # End-values for all lengths
    for val in seq:                             # Try every value, in order
        idx = bisect(end, val)                  # Can we build on an end val?
        if idx == len(end): end.append(val)     # Longest seq. extended
        else: end[idx] = val                    # Prev. endpoint reduced
    return len(end)                             # The longest we found
 
11
This devilishly clever little algorithm was first was first described by Michael L. Fredman in 1975.