UVa 10134: Is Bigger Smarter? (Dynamic programming and longest increasing subsequence)

Question

private void findLDS() {
    Integer[] array = Arrays.copyOf(elephants.iq, elephants.iq.length);
    Hashtable<Integer, Integer> eq = elephants.elephantiqs;

    Integer[] lds = new Integer[array.length];
    Integer[] prev= new Integer[array.length];
    lds[0] = 0;
    prev[0] = 0;

    int maxlds = 1, ending=0;

    for(int i = 0; i < array.length; ++i) {
        lds[i] = 1;
        prev[i] = -1;

        for (int j = i; j >= 0; --j) {
            if(lds[j] + 1 > lds[i] && array[j] > array[i] && eq.get(array[j]) < eq.get(array[i])) {
                lds[i] = lds[j]+1;
                prev[i] = j;
            }
        }
        if(lds[i] > maxlds) {
            ending = i;
            maxlds = lds[i];
        }
    }
    System.out.println(maxlds);
    for(int i = ending; i >= 0; --i) {
        if(prev[i] != -1) {
            System.out.println(eq.get(array[prev[i]])); 
        }

    }

I have based this algorithm on this SO question. This code is trying to find longest decreasing subsequence instead of increasing. array[] is sorted in descending order, and I also have a hashtable with the elephants IQ's as keys for their weights.

I'm having a hard time properly understanding DP, and I need some help.

My algorithm seems to work fine besides tracking the chosen sequence in prev[], where it always misses one element. Does anyone know how to do this?

Answer 1

A few ways to approach this one:

1. Sort by weight in decreasing order, then find the longest increasing subsequence.
2. Sort by IQ in decreasing order, then find the longest increasing subsequence of weights.
3. and 4. are just (1) and (2), switching the words "increasing" and "decreasing"

If you don't understand the DP for longest increasing subsequence O(N^2), it's basically this:

1. Since the list has to be strictly increasing/decreasing anyway, you can just eliminate some elephants beforehand to make the set unique.
2. Create an array, which I will call llis standing for "Longest Increasing Subsequence", of length N, the number of elephants there now are. Create another array called last with the same length. I will assume the sorted list of elephants is called array as it is in your problem statement.
3. Assuming that you've already sorted the elephants in decreasing order, you will want to find the longest increasing subsequence of IQs.
4. Tell yourself that the element in the array llis at index n (this is a different "n") < N will be the length of the longest increasing subsequence for the sub-array of array from index 0 to n, inclusive. Also say that the element in the next array at index n will be the next index in array in the longest increasing subsequence.
5. Therefore, finding the length of the longest increasing subsequence in the "sub-array" of 0 to N - 1 inclusive, which is also the whole array, would only require you to find the N - 1 th element in the array llis after the DP calculations, and finding the actual subsequence would simplify to following the indices in the next array.
6. Now that you know what you're looking for, you can proceed with the algorithm. At index n in the array, how do you know what the longest increasing subsequence is? Well, if you've calculated the length of the longest increasing subsequence and the last value in the subsequences for every k < n, you can try adding the elephant at index n to the longest increasing subsequence ending at k if the IQ of the elephant n is higher than the IQ of the elephant at k. In this case, the length of the longest increasing subsequence ending at elephant n would be llis[k] + 1. (Also, remember to set next[k] to be n, since the next elephant in the increasing subsequence will be the one at n.)
7. We've found the DP relation that llis[n] = max(llis[n], llis[k] + 1), after going through all k s that come strictly before n. Just process the n s in the right order (linearly) and you should get the correct result.
8. Procedure/warnings: 1) Process n in order from 0 to N - 1. 2) For every n, process k in order from n - 1 to 0 because you want to minimize the k that you choose. 3) After you're done processing, make sure to find the maximum number in the array llis to get your final result.
9. Since this is tagged as homework, I won't explicitly say how to modify this to find the longest decreasing subsequence, but I hope my explanation has helped with your understanding of DP. It should be easy to figure out the decreasing version on your own, if you choose to use it. (Note that this problem can be solved using the increasing version, as described in approaches 1 or 2.)