Skip to content

Longest Increasing Subsequence (LIS)

The LIS of an array is the longest strictly increasing subsequence (indices increasing, values strictly increasing). Length is found in \(O(n \log n)\) with a patience sorting style array tail, or in \(O(n^2)\) with simple DP.

\(O(n^2)\) DP

dp[i] = length of longest increasing subsequence ending at index i.

#include <vector>
#include <algorithm>
using namespace std;

int lisN2(const vector<int>& a) {
    int n = (int)a.size();
    if (n == 0) return 0;
    vector<int> dp(n, 1);
    int best = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
        best = max(best, dp[i]);
    }
    return best;
}

tail[k] = smallest possible last value of an increasing subsequence of length k+1. For each x, binary-search the first tail[i] >= x and replace, or extend.

#include <vector>
#include <algorithm>
using namespace std;

int lisNLogN(vector<int> a) {
    vector<int> tail;
    for (int x : a) {
        auto it = lower_bound(tail.begin(), tail.end(), x);
        if (it == tail.end()) tail.push_back(x);
        else *it = x;
    }
    return (int)tail.size();
}

For non-decreasing (allow equal values), use upper_bound instead of lower_bound.