CODEWITHSUNDEEP
javaalgorithm
ddr124
ddr124

Reputation: 11

Need help understanding why the following code does not work

I am trying to solve the Longest Increasing Subsequence problem on leetcode where I have to find the longest increasing subsequence in an array. I am attempting to solve it using Dynamic Programming (O(n^2) complexity).

I have written 2 functions both of which attempt to solve the problem separately however only one function works.

I tried to optimize the second function using the exact same logic of the first function however I am having trouble figuring out why it does not work.

The following function works: 

// WORKS
private int dp(int[] a) {
    int[][] dp = new int[a.length+1][a.length+1];
    for(int p = a.length-1; p >=0; p--) {
        for(int i = a.length-1; i >=0; i--) {
            if(i >= a.length)
                dp[p][i] = 0;
            else if(a[i] > a[p])
                dp[p][i] = Math.max(dp[p][i+1], 1 + dp[i][i+1]);
            else
                dp[p][i] = dp[p][i+1];
        }
    }
    return dp[0][0];
}

In the second function, I try to reduce the space needed by using 2 columns instead of a full matrix as we only need the values of column i+1 to fill a column i. However it does not work (col 1 is an array of 0s) and I cannot figure out why

// DOES NOT WORK
private int dp_optimized(int[] a) {
    int[] col1 = new int[a.length+1];
    int[] col2 = new int[a.length+1];
    for(int p = a.length-1; p >=0; p--) {
        for(int i = a.length-1; i >=0; i--) {
            if(i >= a.length)
                col1[p] = 0;
            else if(a[i] > a[p]) 
                col1[p] = Math.max(col2[p], 1+col2[i]);
            else
                col1[p] = col2[p];
        }
        for(int i=0; i< col1.length; i++)
            col2[i] = col1[i];
    }
    return col1[0];
}

Isnt this basically the same thing? Why does function 1 work and function 2 not work?

Also the main method calling these functions is as follows:

public int lengthOfLIS(int[] nums) {

    int[] a = new int[nums.length+1];
    int[][] dp = new int[a.length+1][a.length+1];
    for(int i = 1; i<nums.length+1; i++)
        a[i] = nums[i-1];
    a[0] = Integer.MIN_VALUE;
    // return dp(a)
    return dp_optimized(a);
}

Any help would be appreciated. Thanks.

Upvotes: 0

Views: 136

Answers (1)

Osama Fathy
Osama Fathy

Reputation: 108

Let's start by making sure that we understand the recurrence correctly.

Definition: dp[p][i] stores the answer to the following question: What is the longest increasing subsequence of integers chosen from the elements with indices [i, a.length() - 1], with an additional constraint that the first element must be greater than a[p] (we will keep track of the last element taken by storing its index in the variable p)

Recurrence: The answer of dp[p][i] is either:

  • dp[p][i+1] : We ignored the i-th item and got the solution of the same problem but by considering only elements with indices [i + 1, a.length - 1]
  • 1 + dp[i][i+1] : We decided to take the i-th item as one of the integers in the optimal subsequence, so we counted the element taken, and now we're interested with elements with indices [i+1, a.length-1]. This choice can only be considered if the i-th element is greater than the p-th element. The p in the sub-problem is changed to i, this to enforce that the next element to be chosen must be greater than the item we just took (the i-th one)

Let's now discuss the code

N^2 Memory Code:

I made slight modifications to your correct code, let's take a look.

private int dp(int[] a) {
    int[][] dp = new int[a.length+1][a.length+1];
    for(int p = a.length-1; p >=0; p--) {
        for(int i = a.length-1; i >p; i--) {
            dp[p][i] = dp[p][i+1]; // Try to leave the i-th item
            if(a[i] > a[p])        // Try to pick the i-th item
                dp[p][i] = Math.max(dp[p][i], 1 + dp[i][i+1]);
        }
    }
    return dp[0][1];
}

1st Modification: I removed the following part if(i >= a.length) col1[p] = 0;, the condition will not be ever satisfied.

2nd Modification: The inner loop iterates between [p+1, a.length-1], since i must be always greater than p

3rd Modification: Instead of returning dp[0][0], return dp[0][1], where the first item is an additional element that was not included in the original array and holds a value smaller than any other item. (dp[0][1] find the LIS of elements [1, a.length-1], given that there's no restriction on the first element to be picked)

Memory Reduction:

Let's think more about the dp table of the above code. The first dimension on the table is the previous index, the second dimension is the starting index in the array a (we're trying to find the LIS starting from i given previous p)

To reduce the memory for your dp solution you must ask yourself 2 questions:

1- Which dimension can be reduced?

To answer this question you must go over each dimension separately and ask yourself if the current value of the dimension is x what other values of the current dimension do I depend on? The farthest value among these values gives us an idea of how much reduction can be done on this dimension.

let's apply the above technique to our problem.

  • Dimension p: if the value of p is x, then in the first subproblem dp[p][i+1] we don't change x (this is great), however in the second subproblem dp[i][i+1] x is changed to i, and i takes any value in the rage [i+1, a.length-1], hence, this dimension is irreducible!

  • Dimension i: if the value of i is x, then in the first subproblem dp[p][i+1] we depend on the values stored in x+1, in the second subproblem dp[i][i+1] we also depend on the values stored in x+1, this is great, It's clear that when the value of i is x we need only values in x+1 to be stored, we don't care at all about values stored in x+2 or x+3 ...

2- What should be the order of our loops?

When we're doing memory reduction, the order of the loops matter, the loop that iterates on the dimension to be reduced must be the outermost one!

When our outer loop is the one that iterates over the second dimension i, the inner loops are responsible of calculating all values of dp[p][i] given that i is constant (in other words, calculates a full column in the dp table), after the calculation, we're ready to move to i-1 since all values in the i-th column are stored and ready to be used, after calculating all values in the (i-1)-th column we can move to i-2 and calculate all answers of i-2 using the answers stored only in the (i-1)-th column, and ignoring all values stored in the i-th column.

So let's reorder the loops of your code:

private int dp(int[] a) {
    int[][] dp = new int[a.length+1][a.length+1];
    for(int i = a.length-1; i>0; i--) {
        for(int p = i-1; p>=0; p--) {
            dp[p][i] = dp[p][i+1]; // Try to leave the i-th item
            if(a[i] > a[p])        // Try to pick the i-th item
                dp[p][i] = Math.max(dp[p][i], 1 + dp[i][i+1]);
        }
    }
    return dp[0][1];
}

Now let's reorder and modify the code you wrote in the dp-optimized function:

private int dp_optimized(int[] a) {
    int[] col1 = new int[a.length+1];
    int[] col2 = new int[a.length+1];
    for(int i = a.length-1; i>0; i--) {
        for(int p = i-1; p>=0; p--) {
            col1[p] = col2[p];
            if(a[i] > a[p]) 
                col1[p] = Math.max(col1[p], 1+col2[i]);
        }
        for(int p=0; p< col1.length; p++){
            col2[p] = col1[p];
        }
    }
    return col1[0];
}

Done!

Upvotes: 3

Related Questions