longest_increasing_sequence.py

def longest_increasing_sequence(seq):
    L = [0] * len(seq)
    P = [0] * len(seq)

    for i in xrange(len(seq)):
        l, k = 0, -1
        for j in xrange(i):
            if seq[j] < seq[i] and L[j] > l:
                l = L[j]
                k = j
        L[i] = l + 1
        P[i] = k
    print "T: ", seq
    print "L: ", L
    print "P: ", P
    
    longest = max(L)
    print "Longest length:", longest
    for i, n in enumerate(L):
        if n is longest:
            subseq = [seq[i]]
            next = P[i]
            while next > -1:
                subseq.insert(0, seq[next])
                next = P[next]
            print subseq

longest_increasing_sequence([9, 5, 2, 8, 7, 3, 1, 6, 4])