Longest Increasing Subsequence

Home | Coding Interviews | Dynamic Programming | Longest Increasing Subsequence

Dynamic Programming Medium Video Python Code Solution

Given an integer array nums, return the length of the longest strictly increasing subsequence.

public int lengthOfLIS(int[] nums) {
    if(nums==null || nums.length==0){
        return 0;
    }
    int[] dp = new int[nums.length];
    int max = 1;
    for(int index=0; index<nums.length;index++){
        dp[index]=1;
        for(int dpIndex=0; dpIndex<index; dpIndex++){
            if(nums[dpIndex]<nums[index]){
                dp[index]=Math.max(dp[index],dp[dpIndex]+1);
                max=Math.max(dp[index],max);
            }
        }
    }
    return max;
}

There is also an O(n log n) solution which uses a technique similar to patience sorting. It isn't simple but once you know the implementation it is natural. Maybe with leetcode difficulty inflation an interviewer may expect you to know this as well because it is such a well known problem.

public class Solution {
    public int lengthOfLIS(int[] nums) {            
        int[] dp = new int[nums.length];
        int len = 0;

        for(int x : nums) {
            int i = Arrays.binarySearch(dp, 0, len, x);
            if(i < 0) i = -(i + 1);
            dp[i] = x;
            if(i == len) len++;
        }

        return len;
    }
}

Posted by Jamie Meyer 21 days ago