Source code online books for professionals by professionals

Listing 8-5.  A Memoized Recursive Solution to the Longest Increasing Subsequence Problem
def rec_lis(seq):                               # Longest increasing subseq.
    @memo
    def L(cur):                                 # Longest ending at seq[cur]
        res = 1                                 # Length is at least 1
        for pre in range(cur):                  # Potential predecessors
            if seq[pre] <= seq[cur]:            # A valid (smaller) predec.
                res = max(res, 1 + L(pre))      # Can we improve the solution?
        return res
    return max(L(i) for i in range(len(seq)))   # The longest of them all
 
Let’s make an iterative version as well. In this case, the difference is really rather slight—quite reminiscent of the 
mirror illustration in Figure 4-3. Because of how recursion works, rec_lis will solve the problem for each position in 
order (0, 1, 2 …). All we need to do in the iterative version is to switch out the recursive call with a lookup and wrap the 
whole thing in a loop. See Listing 8-6 for an implementation.