DP Java solution in 1ms (without using binary search) in 10 lines of code (with explanation)


  • 2
    B

    Consider the sample input given in the question (I added 1 in the 7th slot to make it a little more interesting).

    • Starting at the first number (10), the longest sequence at that point is clearly 1 (thus the number 1 above 10).
    • The next number (9) is smaller than the tail (end) of the longest sequence, so we clearly don't have a sequence of 2 yet. However, the number 9 also is a sequence of 1. Here's an important point, do we really care about the 10 AND the 9? Nope. The only number that matters for a given sequence length (1 in this case) is the smallest number at that sequence length. So 9 is our new minimum for sequence length of 1. These minimum values for each sequence length are stored using the mapSequenceLengthToMinTail array (nope, I'm not proud of that name).
    • The next number (2) is the same case again. It's still just a sequence of 1, but smaller than our old minimum, so we overwrite the 9 with a 2 and move on.
    • Finally! The next number (5) is different. It's greater than our previous minimum value for sequence length 1, so we now have a sequence length of 2 (with a minimum value of 5).
    • The next number (3) just reduces the minimum value for sequence length 2.
    • The next number (7) extends the previous sequence length of 2.
    • The next number (1) finally shows why we need the inner loop below. Our best sequence so far was a length of 3, with a minimum value of 7. 1 clearly doesn't extend this sequence, so now we look at our min value for sequence length of 2, which is 3. 1 clearly doesn't extend that sequence either. The same can be said for sequence length of 1. So at this point we have another sequence of length 1, but again this is a new lower minimum value so we store 1 as the min value for sequence length of 1.

    Hope that makes sense. Love the website. Some great questions, great solutions, and great discussions.

    Seq length at n: 1 1 1 2 2 3 1  4   4
    Sequence:       10 9 2 5 3 7 1 101 18
    
        public int lengthOfLIS(int[] nums) {
            if (nums.length == 0) { return 0; }
            
            int[] mapSequenceLengthToMinTail = new int[nums.length+1];
            int maxLength = 1;
            mapSequenceLengthToMinTail[1] = nums[0];
    
            // for each number in the main list...
            for (int i=1; i<nums.length; i++) {
                // for each sequence length, starting with the biggest so far...
                for (int j=maxLength; j>=0; j--) {
                    if (mapSequenceLengthToMinTail[j] < nums[i]) {
                        mapSequenceLengthToMinTail[j+1] = nums[i]; 
                        maxLength = Math.max(maxLength, j+1);
                        break;
                    }
                }
            }
            
            return maxLength;
        }
    

  • 0
    H

    HI, I think u might set map[0] with INT_MIN to deal with negative numbers. Got 3 (should be 4) from ur code with case 1,2,3,-1,1,2,3. But init map[0] with INT_MIN still not able to do this INT_MIN+2, INT_MIN, INT_MIN+1. The better way would be consider j==0, then change map[0] whatever.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.