Longest Increasing Subsequence, Dynamic Programing

Question

I have the following problem:

Find the longest increasing subsequence of a given sequence / array.

In other words, find a subsequence of array in which the subsequence’s elements are in strictly increasing order, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. In this case, we only care about the length of the longest increasing subsequence.

Example :

Input : [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] Output : 6 The sequence : [0, 2, 6, 9, 13, 15] or [0, 4, 6, 9, 11, 15] or [0, 4, 6, 9, 13, 15]

This is a DP problem and I do have some issue at the memorization step. Here is my code:

public int lis(final List<Integer> a) {
    return maxIncreasing(0, Integer.MIN_VALUE, a);
}
HashMap<Integer, Integer> memo = new HashMap<>();
private int maxIncreasing(int index, int lastElt, final List<Integer> a) {
    if(memo.containsKey(index)) return memo.get(index);
    // end?
    if(index >= a.size()) return 0;
    int weTake = Integer.MIN_VALUE;
    // can we take it?
    if(a.get(index) > lastElt) {
        // take it or don't
        weTake = maxIncreasing(index + 1, a.get(index), a) + 1;
    }
    int weDoNot = maxIncreasing(index + 1, lastElt, a);
    int max = Math.max(weTake, weDoNot);
    memo.put(index, max);
    return max;
}

Without the memo HashMap in place I have the correct result, I am not sure why this is giving me the wrong result once in place.

Thanks.

score 0 · Accepted Answer · answered Dec 11 '16 at 21:46

That is because you are not taking care of the lastElt. Basically, you can have more than one solution for a given index depending on what was the lastElt value. Therefore, you would have to have a Key for your memo that contains both index and lastElt.

You could do something like this:

    class Key {
        final int index;
        final int lastEl;

        Key(int index, int lastEl) {
            this.index = index;
            this.lastEl = lastEl;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Key key = (Key) o;

            if (index != key.index) return false;
            return lastEl == key.lastEl;

        }

        @Override
        public int hashCode() {
            int result = index;
            result = 31 * result + lastEl;
            return result;
        }
    }

    public int lis(final List<Integer> a) {
        return maxIncreasing(0, Integer.MIN_VALUE, a);
    }
    HashMap<Key, Integer> memo = new HashMap<>();
    private int maxIncreasing(int index, int lastElt, final List<Integer> a) {
        Key key = new Key(index ,lastElt);
        if(memo.containsKey(key)) return memo.get(key);
        // end?
        if(index >= a.size()) return 0;
        int weTake = Integer.MIN_VALUE;
        // can we take it?
        if(a.get(index) > lastElt) {
            // take it or don't
            weTake = maxIncreasing(index + 1, a.get(index), a) + 1;
        }
        int weDoNot = maxIncreasing(index + 1, lastElt, a);
        int max = Math.max(weTake, weDoNot);
        memo.put(key, max);
        return max;
    }

Thanks this solution is valid, however still giving me some issue performance wise, probably the recursion is causing memory overhead. — Jerome Ansia, Dec 12 '16 at 20:18
You should try implementing it using dynamic programming. Instead of using a recursion and memoization, you should use an array to calculate all the results as shown here: http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/ — Nikola Stojiljkovic, Dec 13 '16 at 11:04

Longest Increasing Subsequence, Dynamic Programing

1 Answers1

Linked