300. Longest Increasing Subsequence

300. Longest Increasing Subsequence

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

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

• 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?

My Solutions:

和#674不同的是数字可以不连续。

方法1：用dp的思想，初始化每个元素的最大长度都是1。然后对每个元素来说，从右至左iterate当前元素左边位置的元素。如果排在元素i之前的元素j，比元素i小，更新dp[i]为dp[j] + 1 或者dp[i]。

时间：O(n^2); 空间：O(n)

方法2：维护一个长度为n的table，先把第一个数放入table。从左至右iterate原数组的时候，

• 如果发现当前元素大于table里的现有最大元素，则把元素加入table，table的index更新。

• 如果相等，不做任何举动。

• 如果当前元素小于table里的现有最大元素，则用binary search找到table里、比当前元素大的第一个元素，替换掉。这样可以维持递增数组的元素尽量的小。

e.g. nums = [2,5,100,3,4,5]

一开始table是【2，5，100】，当遇到3后，换成【2，3，100】，当遇到4后，换成【2，3，4】，遇到5后，table是【2，3，4，5】

时间：O(nlgn); 空间：O(n)

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        //方法1
        // int[] dp = new int[nums.length];
        // Arrays.fill(dp, 1);
        
        // int max = 1;
        // for (int i = 1; i < nums.length; i++) {
        //     for (int j = i - 1; j >= 0; j--) {
        //         if (nums[j] < nums[i]) {
        //             dp[i]= Math.max(dp[j] + 1, dp[i]);
        //             max = Math.max(max, dp[i]);
        //         }
        //     }
        // }
        // return max;
        
        //方法2
        int[] table = new int[nums.length];
        int len = 0;
        table[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > table[len]) {
                len++;
                table[len] = nums[i];
            } else if (nums[i] == table[len]) {
                continue;
            } else {
                int index = binarySearch(table, nums[i], len);
                table[index] = nums[i];
            }
        }
        
        return len + 1;
    }
    
    // find the index of the first number that is equal/larger than n
    private int binarySearch(int[] table, int n, int r) {
        int l = 0;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (table[mid] < n) l = mid;
            else r = mid;
        }
        if (table[l] >= n) return l;
        else return r;
    }
}