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 is4. 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(nlogn) time complexity?

Credits: Special thanks to@pbrotherfor adding this problem and creating all test cases.

Thoughts

1. O(n^2) solution with recursive and dynamic programming approach by GeeksforGeeks

2. Dynamic Programming (Original GeeksforGeeks explanation) O(n^2)

3. Binary search + Dynamic Programming: O(nlogn) (Original GeeksforGeeks explanation)

Code Binary Search (Java) inspired by GeeksforGeeks: “end element of smaller list is smaller than end elements of larger lists“.

record the tail table by keeping updating current value to correct position into the tail table 
through binary search

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

using Arrays.binarySearch by jopiko123:

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(i < 0) i = -(i + 1);
            dp[i] = x;
            if(i == len) len++;
        }

        return len;
    }
}

Code Binary Search with O(nlogn) by dtccwl, inspired by GeeksforGeeks

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
    vector<int> res;
    for(int i=0; i<nums.size(); i++) {
        auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
        if(it==res.end()) res.push_back(nums[i]);
        else *it = nums[i];
    }
    return res.size();
    }
};