Back to solutions

Longest Increasing Subsequence

MediumDynamic Programming

Return the length of the longest strictly increasing subsequence of an array.

Open problem
Constraints
  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4

Patience sorting with binary search

Time O(n log n)Space O(n)

Maintain the smallest possible tail for each subsequence length. For each value, binary search the first tail >= it and replace it (or append). The number of tails is the answer.

#include <bits/stdc++.h>
using namespace std;

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}