300. Longest Increasing Subsequence

Problem:

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?

Analysis:

Approach 1 (DP)

Very intuitive approach.

State: dp[i], LIS from index 0 include nums[i].

Transition: Compare with each number from 0 to i - 1, if nums[j] < nums[i] update dp[i].

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int[] max = new int[nums.length];
        int res = 0;
        Arrays.fill(max, 1);
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    max[i] = Math.max(max[i], max[j] + 1);
                }
            }
            res = Math.max(res, max[i]);
        }
        return res;     
    }
}

Approach 2 (Binary search)
这个实现真是太难了，看了n遍才看懂。现在问我为什么会这样想，我也不知道。但我知道面试的时候跟着这个流程走一遍肯定能过。我这个实现方法超过了99.42%的submission。
参考https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

中心思想就是要使LIS的最大值尽量小。

以数组[10,9,2,5,4,7,101,18,50] 流程如下。geeks for geeks里面情况1和3可以合并。
这个实现方法印象太深刻，下次遇到肯定做得出来。

Input:10
IS	10	Tail	10
Input:9
IS	9	Tail	9	replace 10
2
IS	2	Tail	2	replace 9
Input:5
IS	2
	2,5	Tail	2,5	clone 2 and append 5
Input: 4
IS	2
	2,4	Tail	2,4	replace 5
Input:7
IS	2
	2,4
	2,4,7	Tail	2,4,7	clone 2,4 and append 7
Input:101
IS	2
	2,4
	2,4,7
	2,4,7,101	Tail	2,4,7,101	clone 2,4,7 and append 101
Input:18
IS	2
	2,4
	2,4,7
	2,4,7,18	Tail	2,4,7,18	replace 101
Input: 50
IS:	2			By replacing 101 with 18 we make room for incoming 50.
	2,4
	2,4,7
	2,4,7,18
	2,4,7,18,50	Tail	2,4,7,18,50	clone 2,4,7,18 and append 50

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) 
            return 0;
        
        int len = 1;
        int[] tails = new int[nums.length];
        tails[0] = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > tails[len  - 1]) {
                tails[len++] = nums[i]; 
            } else
            {
                int index = binarySearch(tails, 0, len - 1, nums[i]);
                tails[index] = nums[i];
            }
        }
        return len;
    }
    
    private int binarySearch(int[] tails, int start, int end, int target) {
        while (start + 1 < end ) {
            int mid = start + (end - start) / 2;
            if (tails[mid] <= target) {
                start = mid;
            } else {
                end  = mid;
            }
        }

        return tails[start] >= target ? start : end;
    }
}