Longest increasing subsequences

Leetcode

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?

Note: Subsequence 不用是连续的

Analysis

动态规划问题，所以要定义四要素：

1. State: 状态
2. Function：状态转移方程
3. Initialization
4. Return result

Solution 1

This solution requires O(n2) time complexity
Ref1

1. State: dp[i] 前i个数字中以第i个数字结尾的LIS长度

2. Function:

   • For all j<i, f[i] = 1 + max(f[j]) where nums[j] < nums[i]$ if no nums[j]$$ is smaller than nums[i], then $$f[j]=1
   • For example:
     nums: 4 2 4 5 3 7
     dp: 1 1 2 3 2 4

3. Initialization: dp[0] = 1，很重要，要是前面都没有比它小的，从它开始至少有1。

4. Result: return max(dp[])

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length==0) {return 0;}
        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[j]+1>dp[i]) {
                    dp[i] = dp[j]+1;
                }
            }
        }
        int result = 1;
        for (int i=0; i<nums.length; i++){
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

Solution2

Do not understand
Better solution with O(nlgn) time complexity
Ref2
The idea is that as you iterate the sequence, you keep track of the minimum value a subsequence of given length might end with, for all so far possible subsequence lengths.
So dp[i] is the minimum value a subsequence of length i+1 might end with. Having this info, for each new number we iterate to, we can determine the longest subsequence where it can be appended using binary search. The final answer is the length of the longest subsequence we found so far.

1. State: minimum value a subsequence of length i+1 might end with

public class Solution {
    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 cannot find x, i equals to insertion point, insert x into i position
            if(i < 0) i = -(i + 1);
            dp[i] = x;
            if(i == len) len++;
        }

        return len;
    }
}

Questions

Solution2 do not understand