4/13 LIS

先从 O(n^2) 的 DP 做法说起。先从这个开做，是因为 O(n^2) 做法的普适性高，而且可以无视维度，易于扩展到各种变形与 follow-up 上。

需要返回具体 LIS sequence 的时候，加一个新 array，记录 parent index 一路追踪就可以了~ 和 Largest Divisible Subset 一样。

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0) return 0;

        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        int max = 1;

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

        return max;
    }
}

• 这里要注意 “等于号”，不然返回的index会错

• if(dp[start] >= target) return start;

• if(dp[end] < target) return end + 1;

• return end;

• 如果 binary search 里面指针一直在 agressively 往右走，那么最终的返回位置不外乎 left, right 和 right + 1. 所有小于等于 num[left] 的情况都返回 left.

这个问题的 follow up 也很有意思，返回一条最长的 subsequence，还有返回所有的 subsequence.

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

A O(n^2) solution is, do Longest Common Subsequence between original array and sorted one, the LCS would be the LIS.

This is also "Online Algorithm" which we keep taking streams of input data one at a time.

For improvement, the key is take advantage of the "Increasing Sequence"

Terminating condition for "Search insert position" is important and needs to be accurate.

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int ptr = 0;
        for(int i = 1; i < nums.length; i++){
            int pos = binarySearch(dp, 0, ptr, nums[i]);
            if(dp[pos] > nums[i]) dp[pos] = nums[i];
            if(pos > ptr){
                ptr = pos;
                dp[pos] = nums[i];
            }
        }

        return ptr + 1;
    }

    private int binarySearch(int[] dp, int start, int end, int target){
        while(start + 1 < end){
            int mid = start + (end - start) / 2;
            if(target > dp[mid]){
                start = mid;
            } else {
                end = mid;
            }
        }

        // This equality sign is important
        // otherwise it would return wrong insert position
        if(dp[start] >= target) return start;
        if(dp[end] < target) return end + 1;

        return end;
    }
}