最长递增子序列

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]

Output: 4

Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]

Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]

Output: 1

Constraints:

• 1 <= nums.length <= 2500
• -\(10^4\) <= nums[i] <= \(10^4\)

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Idea

The basic dynamic programming solution lets dp[i] be the length of the longest increasing subsequence ending at nums[i], which takes \(O(n^2)\) time. It can be sped up with binary search.

Keep an array tails, where tails[k] is the smallest possible last value of an increasing subsequence of length k + 1. The array is always sorted in increasing order.

For each number x, binary search tails for the first value that is greater than or equal to x. If there is none, append x, which extends the longest subsequence by one. Otherwise, replace that value with x, so subsequences of that length end with a smaller value and are easier to extend later.

The length of tails at the end is the answer.

Time complexity: \(O(n \log n)\), Space complexity: \(O(n)\)

Pseudo Code

tails = [];
for (x in nums) {
    left = 0;
    right = tails.length;
    while (left < right) {
        mid = left + (right - left) / 2;
        if (tails[mid] < x) {
            left = mid + 1;
        }
        else {
            right = mid;
        }
    }
    if (left == tails.length) {
        tails.append(x);
    }
    else {
        tails[left] = x;
    }
}
return tails.length;