300. Longest Increasing Subsequence - jiejackyzhang/leetcode-note GitHub Wiki

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?

##Approach1: O(n^2) 解题思路为Dynamic Programming。

令LIS[i]表示length of LIS starting from i。则：

LIS[i] = max(LIS[i], LIS[j] + 1) for any j > i && nums[j] > nums[i]

则最终的length of LIS就是max{LIS[i]} for i = 0, ..., nums.length-1。

注意点是LIS[i]初始值是1，即本身。

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

from left to right

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

##Approach 2: O(nlogn) 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]

解题思路为顺序扫描nums，若当前为nums[k]，则tails[0,...,k-1]记录了之前长度为1到k的IS的其中最小的那个subsequence的尾数。可以证明，tails本身也是increasing的。我们的问题转换为在tails[0,...,k-1]中找那个刚好比nums[k]小的数，可用binary search，时间复杂度为O(logn)。

若nums[k]比tails[0,...,k-1]都大，则存在一个长度为k+1的IS，tails[k]=nums[k]，size增加1；
若tails[i-1] < nums[k] <= nums[k]，则用nums[k]更新tails[i]。

本质上为找到nums[k]应该插入的位置，若nums[k]插在末尾，则size++。

因此有n个iteration，每个iteration时间为logn，总的时间复杂度为O(nlogn)。

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for(int num : nums) {
            int i = 0, j = size;
            while(i < j) {
                int m = i + (j - i) / 2;
                if(tails[m] < num) {
                    i = m + 1;
                } else {
                    j = m;
                }
            }
            tails[i] = num;
            if(i == size) size++;
        }
        return size;
    }
}

300. Longest Increasing Subsequence - jiejackyzhang/leetcode-note GitHub Wiki

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️