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($n^2$) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

DP O($n^2$)

经典的动态规划的题目

State: dp[i] 指以当前数字结尾的最长递增子序列
Function: dp[i] = Max(nums[0 .. i - 1] < nums[i] ? dp[0 .. i - 1] + 1 : 1)
Init: dp[i] = 1;
Answer: Max(dp[i])

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

Binary Search O(nlogn)

我自己讲不清楚，下面是网上找来的一句话，讲的也不是很好，只讲了How, 没有讲Why. 有兴趣和毅力的话看看geeeksforgeeks上的文章吧

维护一个单调序列, 遍历nums数组，二分查找每一个数在单调序列中的位置，然后替换之。

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

Ref: