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(n2) complexity.

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

Solution #1:

Use count array to record the length of previous LIS. Initialize new count val to 1, and compare it to all previous smaller elements' LIS count + 1. Replace it if count + 1 is bigger. Return the max value in count array.

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int   max   = 0;
    int[] count = new int[nums.length];

    for (int i = 0; i < nums.length; i++) {
        count[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                count[i] = Math.max(count[j] + 1, count[i]);
            }
        }
        max = Math.max(max, count[i]);
    }
    return max;
}

Solution #2:

Maintain a longest increasing sequence in a list and update it accordingly. While iterate through nums, insert it into the list either by appending or replace the first element that is bigger or equal than it. Use binary search to find the first element that's bigger than the element.

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    List<Integer> LIS = new ArrayList<>();
    for (int num : nums) {
        if (LIS.size() == 0 || num > LIS.get(LIS.size() - 1)) {
            LIS.add(num);
            continue;
        }
        int left  = 0,
            right = LIS.size() - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (LIS.get(mid) < num) {
                left = mid;
            } else {
                right = mid;
            }
        }
        int insertPosition = LIS.get(left) >= num ? left : right;
        LIS.set(insertPosition, num);
    }
    return LIS.size();
}