Longest Increasing Subsequence

题目地址：
https://leetcode.com/problems/longest-increasing-subsequence/#/description

题目：

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.

解题思路：
其中一种解法是n^2，就是用dynamic programming的思想，每次往回看，找所有比自己小的数，然后从相应的index取到；如果需要优化，则需要用二分法来查找，找出potential可能插入的位置，但是最后的array里面不一定是最后结果，所以我们需要维持一个last作为结果。但是第一种可以保留最后结果。

代码：

regular solution:

public int lengthOfLIS(int[] nums) {
    if(nums == null || nums.length == 0){
        return 0;
    }
    int[] dp = new int[nums.length];
    dp[0] = 1;
    int rst = 1;
    for(int i = 1; i <= nums.length - 1; i++){
        int max = 1;
        int curr = nums[i];
        for(int j = 0; j <= i - 1; j++){
            if(nums[j] < curr){
                max = Math.max(max, dp[j] + 1);
            }
        }
        dp[i] = max;
        rst = Math.max(rst, dp[i]);
    }
    return rst;
}

binary search solution:

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    // last is the index of the last element    
    int last = 0;
    for (int i = 1; i < nums.length; i++) {
        int pos = binarySearch(dp, last, nums[i]);
        // there are two if because it could be negative value        
        if (nums[i] < dp[pos]) dp[pos] = nums[i];
        if (pos > last) {
            last = pos;
            dp[last] = nums[i];
        }
    }
    return last + 1;
}
// to find the index of the first element that is larger or equals to val
private int binarySearch(int[] dp, int last, int val) {
    int left = 0;
    int right = last;
    while(left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (dp[mid] == val) {
            return mid;
        } else {
            if (dp[mid] < val) {
                left = mid;
            } else {
                right = mid;
            }
        }
    }
    if (dp[right] < val) return right + 1;
    else if (dp[left] >= val) return left;
    else return right;
}