300. Longest Increasing Subsequence

Problem

Leetcode - 300. Longest Increasing Subsequence

Approach

DP

public class LongestIncreasingSubsequence {
    public int lengthOfLIS(int[] nums) {  
        int[] dp = new int[nums.length];  
        Arrays.fill(dp, 1);  
        int ans = 1;  

        for (int i = 0; i < nums.length; i++) {  
            for (int j = 0; j < i; j++) {  
                if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {  
                    dp[i] = dp[j] + 1;  
                    ans = Math.max(ans, dp[i]);  
                }            
            }        
        }        
        return ans;  
    }
}

• Time complexity: O(n^2)
• Space complexity: O(n)

Greedy with Binary Search

• Let's construct the idea from following example.
• Consider the example nums = [2, 6, 8, 3, 4, 5, 1], let's try to build the increasing subsequences starting with an empty one: sub1 = [].
  1. Let pick the first element, sub1 = [2].
  2. 6 is greater than previous number, sub1 = [2, 6]
  3. 8 is greater than previous number, sub1 = [2, 6, 8]
  4. 3 is less than previous number, we can't extend the subsequence sub1, but we must keep 3 because in the future there may have the longest subsequence start with [2, 3], sub1 = [2, 6, 8], sub2 = [2, 3].
  5. With 4, we can't extend sub1, but we can extend sub2, so sub1 = [2, 6, 8], sub2 = [2, 3, 4].
  6. With 5, we can't extend sub1, but we can extend sub2, so sub1 = [2, 6, 8], sub2 = [2, 3, 4, 5].
  7. With 1, we can't extend neither sub1 nor sub2, but we need to keep 1, so sub1 = [2, 6, 8], sub2 = [2, 3, 4, 5], sub3 = [1].
  8. Finally, length of longest increase subsequence = len(sub2) = 4.
• In the above steps, we need to keep different sub arrays (sub1, sub2..., subk) which causes poor performance. But we notice that we can just keep one sub array, when new number x is not greater than the last element of the subsequence sub, we do binary search to find the smallest element >= x in sub, and replace with number x.
• Let's run that example nums = [2, 6, 8, 3, 4, 5, 1] again:
  1. Let pick the first element, sub = [2].
  2. 6 is greater than previous number, sub = [2, 6]
  3. 8 is greater than previous number, sub = [2, 6, 8]
  4. 3 is less than previous number, so we can't extend the subsequence sub. We need to find the smallest number >= 3 in sub, it's 6. Then we overwrite it, now sub = [2, 3, 8].
  5. 4 is less than previous number, so we can't extend the subsequence sub. We overwrite 8 by 4, so sub = [2, 3, 4].
  6. 5 is greater than previous number, sub = [2, 3, 4, 5].
  7. 1 is less than previous number, so we can't extend the subsequence sub. We overwrite 2 by 1, so sub = [1, 3, 4, 5].
  8. Finally, length of longest increase subsequence = len(sub) = 4.

public class LongestIncreasingSubsequenceII {   
    public int lengthOfLIS(int[] nums) {  
        List<Integer> list = new ArrayList<>();  
        if (nums.length == 0) {  
            return 0;  
        }  
        for (int num : nums) {  
            if (list.isEmpty() || num > list.get(list.size() - 1)) {  
                list.add(num);  
            } else {  
                int i = lowerBoundIndex(list, num);  
                list.set(i, num);  
            }        
        }  
        return list.size();  
    }

    int lowerBoundIndex(List<Integer> list, int k) {  
        int l = 0;  
        int r = list.size() - 1;  
        while (l <= r) {  
            int mid = l + (r - l) / 2;  
            if (list.get(mid) > k) {  
                r = mid - 1;  
            } else {  
                l = mid + 1;  
            }        
        }  
        return l;  
    }
}

Path of LIS

List<Integer> pathOfLIS(int[] nums) {  
    int n = nums.length;  
    List<Integer> sub = new ArrayList<>();  
    List<Integer> subIndex = new ArrayList<>();  
    int[] path = new int[n]; // path[i] point to the index of previous number in LIS  
    Arrays.fill(path, -1);  

    for (int i = 0; i < nums.length; i++) {  
        if (sub.isEmpty() || sub.get(sub.size()-1) < nums[i]) {  
            path[i] = sub.isEmpty() ? -1 : subIndex.get(sub.size()-1);  
            sub.add(nums[i]);  
            subIndex.add(i);  
        } else {  
            int idx = lowerBoundIndex(sub, nums[i]);  
            path[i] = idx == 0 ? -1 : subIndex.get(idx-1);  
            sub.set(idx, nums[i]);  
            subIndex.set(idx, i);  
        }    
    }    
    List<Integer> ans = new ArrayList<>();  
    int t = subIndex.get(subIndex.size()-1);  
    while(t != -1) {  
        ans.add(nums[t]);  
        t = path[t];  
    }   
    Collections.reverse(ans);  
    return ans;  
}