memoization for recursive Longest Increasing subsequence

Question

I came up with simple following recursive solution for Longest increasing sub-sequence. But, Can you help to include memoization into this recursive solution.

public int findLIS(int a[], int maxSoFar, int item, int count) {

        if(item == a.length) {
            return count;
        }
        int length1 = findLIS(a,maxSoFar, item+1, count);
        int length2 = 0;
        if(a[item] > maxSoFar) {

            length2 = findLIS(a, a[item], item+1, count + 1);
        }
        return Math.max(length1, length2);
}

PS: This not a homework question, it is more of my interest.

Java, but you can easily convert to your favorite language. I can do it for you if you want — coder000001

amit amit · Accepted Answer · 2012-12-08T21:17:30

Use a Map<Pair<Integer,Integer>,Integer>, and at the beginning of the method add:

Integer cache = map.get(new Pair<Integer,Integer>(maxSoFar,item));
if (cache != null) return cache;

Each time you return anything - make sure to write (maxSoFar,item)=returnValue to the map.

The idea is to map between the pair that represent where you are in the calculation - to the maximal value found for this state, to avoid recalculating it.

It seems java, so you can use apache commons Pair as your Pair interface.

memoization for recursive Longest Increasing subsequence

1 Answers