Ref: link

300. Longest Increasing Subsequence (Medium)

This problem is not difficult. We can find dp function in a short time. At first, initiate all dp values to 1, because if the input array is in decreasing order, the answer is 1. Dp function is dp[i] = Math.max(dp[i],dp[j]+1) j<i and nums[j]<nums[i]. The return value should be the maximum value of dp array.

The follow up is difficult. We need to use binary search to improve time complexity. We need a new list. And we add values to this list. Finally, the size of this list is the answer. At first, we add nums[0] to the list. And then we iterate the input array. If nums[i]<=nums[0], we replace nums[0] with nums[i]. If nums[i]>nums[last inex], we add nums[i] to the list. If nums[0]<nums[i]<=nums[last index], we use binary search to find the first value which is larger than nums[i] and we replace this value with nums[i]. Note, the result list may not be the longest increasing subsequence. But we don’t need the longest increasing subsequence. We only need its length. The idea is, if we iterate a value which is larger than all values in the list, we add it so we can build a longer increasing subsequence. If we find a value which is smaller than the last value in the list, we replace the first value which is larger than the target value with the target value. In this way, we try to make the value in the list as small as possible. If values are very small, we have more opportunities to build a longer increasing subsequence.

Time complexity is O(nlogn). Space complexity is O(n). Here is the link.

    public int lengthOfLIS(int[] nums) {
        if(nums.length==0)return 0;
        List<Integer>list = new ArrayList();
        list.add(nums[0]);
        for(int i =1;i<nums.length;i++){
            if(nums[i]<=list.get(0)){
                list.set(0,nums[i]);
            }
            else if(nums[i]>list.get(list.size()-1)){
                list.add(nums[i]);
            }
            else{
                int left = 0;
                int right = list.size();
                while(left<right-1){
                    int mid = left + (right-left)/2;
                    if(list.get(mid)<nums[i]){
                        left = mid + 1;
                    }
                    else
                        right = mid;
                }
                int index = list.get(left)>nums[i]?left:right;
                list.set(index,nums[i]);
            }
        }
        return list.size();
    }

646. Maximum Length of Pair Chain (Medium)

There are some differences between this and last problem. In last problem, we need to find a subsequence which means we cannot change the order in the input array. But in this problem, we can select pairs in any order which means we can change the order of input array. Therefore, we can sort the input array according to the first element in ascending order. And then we can use the same way as the last problem. But we cannot use binary search, because we need to consider two values this time, the left border and the right border.

Time complexity is O(n^2). Space complexity is O(n). Here is the link.

We can improve this solution by using greedy instead. Here is the link.

public int findLongestChain(int[][] pairs) {
    Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
    int []dp = new int [pairs.length];
    int ans = 1;
    for(int i =0;i<pairs.length;i++)dp[i]=1;
    for(int i =1;i<pairs.length;i++){
        for(int j = 0;j<i;j++){
            if(pairs[i][0]>pairs[j][1]){
                dp[i] = Math.max(dp[i],dp[j]+1);
                ans = Math.max(dp[i],ans);
            }
        }
    }
    return ans;
}

1143. Longest Common Subsequence (Medium)

We can use dp to solve this problem. We have two strings so we use 2D array for dp. dp[i][j] means the length of the longest common subsequence of text1 with first i characters and text2 with first j characters. We return the last value in 2D array. dp function is

dp[i][j] = dp[i-1][j-1]+1 if text1[i]=text2[j]
dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j])

Assume text1 = ‘abc’ and text2 = ‘ac’. When we find text1[2] = text2[1] = ‘c’, we need to know the length of the longest common subsequence of text1 = ‘ab’ and text2 = ‘a’. And plus 1 to this length. Assume text1[i]!=text2[j]. This means we cannot get a longer common subsequence with ith character in text1 and jth character in text2. Therefore, we can check two situations without these two characters separately. And use the larger value as the value of dp[i][j].

Time complexity is O(mn). Space complexity is O(mn). m is the length of text1. n is the length of text2. Here is the link.

    public int longestCommonSubsequence(String text1, String text2) {
        int[][]dp = new int[text1.length()+1][text2.length()+1];
        for(int i =0;i<text1.length();i++){
            for(int j =0;j<text2.length();j++){
                dp[i+1][j+1] = Math.max(dp[i][j+1],dp[i+1][j]);
                if(text1.charAt(i)==text2.charAt(j)){
                    dp[i+1][j+1] = dp[i][j]+1;
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }