300. Longest Increasing 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?

Solution1: regular DP

思路：
dp[i] is the length of the increasing subsequence ending up with nums[i], initialize: dp[i] is at least 1, formula: if nums[j] < nums[i] (0<=j<i) , then update dp[i] to be max(dp[j] + 1, dp[i]))

Solution2：DP tail数组 ＋ binary search更新

思路：
tails is an array storing the smallest tail of all increasing subsequences with length i+1 in tails[i].
For example, say we have nums = [4,5,6,3], then all the available increasing subsequences are:

len = 1 : [4], [5], [6], [3] => tails[0] = 3
len = 2 : [4, 5], [5, 6] => tails[1] = 5
len = 3 : [4, 5, 6] => tails[2] = 6
We can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update.

Each time we only do one of the two:

(1) if x is larger than all tails, append it, increase the size by 1
(2) if tails[i-1] < x <= tails[i], update tails[i]

Time Complexity: O(NlogN) Space Complexity: O(N)

Solution2.5：DP tail数组 ＋ binary search更新 Round1

Time Complexity: O(NlogN) Space Complexity: O(N)

Solution1 Code：

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        //def: dp[i] represents the lenth of a increasing subsequence ending up with nums[i]
        int[] dp =new int[nums.length]; 
        int max = 1;
        //initialize
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
        }
        //formula
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);    
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;       
    }
}

Solution2 Code：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        
        for(int x: nums) {
            int pos = Arrays.binarySearch(dp, 0, len, x);
            if(pos < 0) pos = -1 * pos - 1;
            dp[pos] = x;
            if(pos == len) len++;
        }
        
        return len;
    }
}

Solution2.5 Round1 Code：

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 valid_len = 1;
        
        for(int i = 0; i < nums.length; i++) {
            int pos = binary_sesarch(dp, nums[i], 0, valid_len - 1);
            dp[pos] = nums[i];
            
            if(pos == valid_len) {
                valid_len++;
            }
        }
        
        return valid_len;
        
    }
    
    private int binary_sesarch(int[] nums, int target, int left, int right) {
        while(left + 1 < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return mid;
            }
            else if(nums[mid] < target) {
                left = mid;
            }
            else {
                right = mid;
            }
        }
        
        if(nums[left] >= target) {
            return left;
        }
        else if(nums[right] >= target) {
            return right;
        }
        else {
            return right + 1;
        }
    }
}