Find the longest increasing subsequence.

longest_inc_seq.py

"""Find the longest increasing subsequence.

Given a sequence of n real numbers A(1) ... A(n), determine a subsequence (not
necessarily contiguous) of maximum length in which the values in the
subsequence form a strictly increasing sequence.

[http://people.csail.mit.edu/bdean/6.046/dp/]

Optimal subproblem:

    M(i) := Length of the longest increasing subsequence that ends at i-th index.

    M(i) = max(M(j)) + 1
            s.t. A_j < A_i and j < i
           
           or

           1, if {A_j} == {}

"""

class EmptyAError(Exception):pass

class LongestIncSeq:
    def __init__(self, A):
        if not A: raise EmptyAError
        self.A = A
        self.n = len(A)
        self.tab = [-1 for i in xrange(self.n)]
        self.traceback = [None for i in xrange(self.n)]

    def M(self, i):
        if self.tab[i] != -1: return self.tab[i]
        less_set = [j for j in xrange(i) if self.A[j] < self.A[i]]
        if not less_set:
            self.tab[i] = 1
            self.traceback[i] = None
        else:
            prev = max(less_set, key = self.M)
            self.tab[i] = self.M(prev) + 1
            self.traceback[i] = prev
        return self.tab[i]

    def solve(self):
        end_ind = max(xrange(self.n), key = self.M)
        traceback = [end_ind]
        prev = self.traceback[end_ind]
        while prev != None:
            traceback.append(prev)
            prev = self.traceback[prev]
        traceback.reverse()
        return (self.M(end_ind), traceback)

class TestLongestIncSeq:
    def test_normal(self):
        A = [3,1,5,2,7,4,6,8]
        assert LongestIncSeq(A).solve() == (5, [1,3,5,6,7])

    def test_equal(self):
        A = [1,1,1,1]
        assert LongestIncSeq(A).solve() == (1, [0])

    def test_single(self):
        A = [0]
        assert LongestIncSeq(A).solve() == (1, [0])

    def test_decreasing(self):
        A = [0,-1,-2,-3,-4]
        assert LongestIncSeq(A).solve() == (1, [0])