(deprecated in favor of https://gist.github.com/2723571) Algorithm to find the longest increasing subsequence (http://people.csail.mit.edu/bdean/6.046/dp/)

longest_increasing_subsequence.py

class LIS:
    def __init__(self, A):
        self.A = A
        self.N = len(A)
        self.table = self.init_table()

    def init_table(self):
        table = [[0,-1] for i in xrange(self.N)]
        table[0][0] = 1
        return table

    def find_LIS_end_at(self, i):
        '''returns (max_len, prev_idx)'''
        if self.table[i][0] != 0: return self.table[i]
        try:
            idx = max( [j for j in xrange(i) if self.A[j] < self.A[i]], 
                       key = lambda j: self.find_LIS_end_at(j)[0] )
        except ValueError:
            self.table[i] = [1,-1]
        else:    
            self.table[i] = [self.find_LIS_end_at(idx)[0] + 1, idx]
        return self.table[i]

    def get_LIS(self):
        idx = max( xrange(self.N),
                   key = lambda i : self.find_LIS_end_at(i)[0] )
        trace_back = []
        while idx != -1:
            trace_back.append(self.A[idx])
            idx = self.find_LIS_end_at(idx)[1]
        trace_back.reverse()
        return trace_back

if __name__ == "__main__":
    from random import randint

    A = [ randint(0,19) for i in xrange(10) ]
    print A
    x = LIS(A)
    print x.get_LIS()