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?

Don't really know how to solve this for a long time. The equation is:

res[i] = Max(res[j]) + 1; if nums[i] > nums[j]

       = Max(1,res[i]); if nums[i] <= nums[j]

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

The O(nlogn) algorithms keep an result array, all the number is initialized to MAX_VALUE, then for each number in the data array, try to find the first index that result[index] > number[i]; if so, update result[index] = number[i]; continue doing this, first index whose value is not MAX_VALUE is the result max increasing sequence.

Given [10, 9, 2, 5, 3, 7, 101, 18],
[M,M,M,M,M,M,M,M];
for 10, index is 0;
[10,...]
for 9; index is still 0;
[9,...]
for 2, [2,...]
for 5, [2,5...]
for 3, index is 1, [2,3...]
for 7, [2,3,7...]
for 101 [2,3,7,101,...]
for 81 [2,3,7,81...(M)]

so the size is 3 +1;

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length <=1) return nums.length;
        int[] res = new int[nums.length];
        for(int i=0; i< nums.length;i++){
            res[i] = Integer.MAX_VALUE;
        }
        for(int i=0; i< nums.length; i++){
            int index =binarySearchIndex(res, nums[i]);
            res[index] = nums[i];
        }
        int count = 0;
        for(int i=res.length-1; i>=0;i--){
            if(res[i] != Integer.MAX_VALUE) count++;
        }
        return count;
    }

    int binarySearchIndex(int[] nums, int val){
        int left=0;
        int right = nums.length-1;
        while(left < right){
            int mid = left + (right-left)/2;
            if(nums[mid] == val){
                return mid;// because our special case in this question, there will be only one number, and no repeat.
            }else if(nums[mid] > val){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return left;

    }
}