Longest Increasing Sub-Sequence using Dynamic Programming in Python

Question

I wrote the following function to find the longest increasing sub-sequence in an array (tuple, it doesn't work for a list since a list is mutable and it stores the results in a dictionary.). It uses Top Down dynamic programming approach.

def LIS(seq, memo={}):   
    if len(seq) == 1:
        return seq

    elif seq in memo:
        return memo[seq]

    else:
        longest = (seq[-1],)
        for index in range(1, len(seq)):
            till_index = LIS(seq[:index], memo)
            till_index += (seq[-1],) if till_index[-1] < seq[-1] else ()
            longest = max(longest, till_index, key=len)
        memo[seq] = longest
        return memo[seq]

It works correctly for all the test cases I've tried. Could you please suggest some changes which can help me reduce its time and memory consumption?

Answer 1

It works correctly for all the test cases I've tried.

Fortunately I thought this was a different algorithm, and so tested with "dogcatcatdog". The answer you give is "dot" where it can be "acdo" or "acdg".
This is better shown with the transformation ord(c) - 97, where yours gives (3, 14, 19) where it can be (0, 2, 3, 14) or (0, 2, 3, 6).
I'll come back to tests as my changes will not fix this.

There are a couple of ways to improve your program:

• Make and use a closure.
• Allow the code to work with things other than tuples.
• Limit the calls to the dictionary.

I'd use a closure as then you don't need to pass the cache, or memo in your case, to the function every function call. It makes sure that all calls to the function whilst recursing are using the same cache and there are no dodgy edge-case cache problems. These are unlikely but it adds clarity none the less.

A simple call of tuple allows your code to work on a much larger array of data-types, all the built-in ones and any that allow the conversion to a tuple. Your excuse that lists are mutable and so don't work is poor, as the only reason that you have to convert your code to a tuple is as you append (seq[-1],) to the output. I'd also like to point out that your code doesn't work with strings that are immutable in the same way tuples are.

Finally if you are concerned with performance. A simple easy way to improve usage is to use memo.get. You use seq in memo to then use memo[seq]. Instead you can use memo.get(seq, None). This is as whilst dictionary's are \$O(1)\$, they still take a long time to get to the correct key. This is as they hash the object, perform a transform on that hash, then use that modified hash to extract the data. And so can take a while.

If I were to do all the above then I'd get to:

def lin(seq):
    seq = tuple(seq)
    cache = {}
    def inner(seq):
        if len(seq) == 1:
            return seq

        ret = cache.get(seq, None)
        if ret is not None:
            return ret

        longest = (seq[-1],)
        for index in range(1, len(seq)):
            till_index = inner(seq[:index])
            till_index += (seq[-1],) if till_index[-1] < seq[-1] else ()
            longest = max(longest, till_index, key=len)
        cache[seq] = longest
        return longest
    return inner(seq)

This functions the same way as before, and it keeps most of the same logic. It's cleaner and allows you to add more corrections to the input, without doing them every recursion.

I also tried using a generator, however it changed your programs functionality. The code that I used is:

last = seq[-1]
sub_sequences = (
    j + (last,) if j and j[-1] < last else ()
    for j in (inner(seq[:i]) for i in range(len(seq)))
)
longest = max((last,), *sub_sequences, key=len)

This gives the correct output when you enter 'dogcatcatdog'. But if you change the input to 2, 5, 3, 7, 11, 8, 13, 6 then your original gives the correct result, where the generator doesn't. Here's what they return:

> dogcatcatdog
dot (original)
acdg

> 2, 5, 3, 7, 11, 8, 13, 6
2, 5, 7, 11, 13 (original)
2, 5, 6

From this we can tell that your algorithm probably isn't the best. As it doesn't work 100% of the time, and if you make it lazy it doesn't work other times.

I'll leave you to figure out if and how you want to amend this. But I'd point you in the way of Wikipedia if you want an efficient method to do this. It uses a binary search to find the max, and some funky stuff to get the list. I'd also change lo ≤ hi to lo < hi in it's version as you don't want repeating numbers.