2

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.

coder000001
  • 476
  • 4
  • 22

1 Answers1

4

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.

amit
  • 175,853
  • 27
  • 231
  • 333
  • Thanks.Before posting here, I quickly checked with an array of { 10, 22, 9, 33, 21, 50, 41, 60, 80 }; and a memo = new int[10][81]; But, it didn't work for me. I'll check with your solution too. – coder000001 Dec 08 '12 at 21:35
  • 2
    @coder000001: It is equivalent to the map solution. Please post the code you used, there might be a bug in it – amit Dec 08 '12 at 21:36
  • it may not equivalent. whn array gets bigger allocating memory may lead to core dump. so Map is a better soln. – Access Denied Dec 11 '12 at 04:43
  • here is the implementation using the map https://pastebin.com/BZatp7by in case if someone is interested. – irsis Nov 06 '20 at 16:06