Longest Increasing Subsequence (LIS) in $O(N \log N)$ - Course 3

Module 1: 2D DP

Longest common subsequence (LCS)
Longest Increasing Subsequence (LIS)
Longest Increasing Subsequence (LIS) in $O(N \log N)$
Knapsack problem
Lazy DP

Module 2: DSU

System of disjoint sets

Module 3: MST

Minimum and maximum spanning trees
Kruskal's Algorithm
Prim's Algorithm
Borůvka's Algorithm

Module 4: Combinatorics

Stars and columns
The principle of inclusion-exclusion

Module 5: Geometry

Finding the area of a simple polygon

Module 6: Arbitrary-Precision Arithmetic

Long Arithmetic

Module 7: Data structures for keeping minimum

Stack with Minimum
Queue with Minimum
Deque with Minimum

Module 8: Heap [BONUS]

Binary Heap

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Course 3/Module 1: 2D DP/Longest Increasing Subsequence (LIS) in $O(N \log N)$

Longest Increasing Subsequence (LIS) in $O(N \log N)$

Longest Increasing Subsequence (LIS) in $O(N \log N)$

Previously we discussed solving the LIS problem using dynamic programming, which runs in $O(N^2)$ . We arrived at the formula $dp(i)$ = the length of the longest increasing subsequence ending at $i$ (where $a_i$ is included in the sequence).

Up next

Knapsack problem

Knapsack problem

dp[i] = \max\left(1, \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(dp[j] + 1\right)\right)

Optimized solution using binary search $O(N \log N)$

To achieve a better result than $O(N^2)$ , we need to choose a different state for our $dp$ . Let $dp(l)$ = the smallest element at which some increasing sequence of length $l$ ends. Initially, the $dp$ array looks like this:

dp[l] = \begin{cases} -\infty &\text{for $l = 0$} \\ \infty &\text{for $1 \leq l \leq N$} \end{cases}

Then we process the elements of the array one by one and update our $dp$ . When processing $a_i$ we need to check for each $l$ whether it is possible to extend a sequence of length $l - 1$ using $a_i$ . Formally, for each $l$ we check if $dp[l - 1] < a_i$ and choose the smallest $a_i$ for which this is true, and set $dp[l]$ equal to that value. It is easy to see why choosing the smallest such $a_i$ is optimal.

Example

Processing 4: The number 4 is the first element, so it is the smallest number at which a subsequence of length 1 ends.
Processing 1: The number 1 can replace 4 in the DP array, since 1 is smaller and also ends a subsequence of length 1.
Processing 3: The number 3 is greater than 1, so it increases the subsequence length to 2. Now it is the smallest number ending a subsequence of length 2.
Processing 2: The number 2 is less than 3 and greater than 1, so it replaces 3 in the DP array as the ending element of a subsequence of length 2.
Processing 5: The number 5 increases the increasing sequence; now it is the smallest number that ends a subsequence of length 3.

After these steps, the $dp$ array indicates that the longest increasing subsequence has length 3, which is the largest index with a value less than $\infty$ .

Naive implementation

Observations

Note that $dp$ is always sorted, since $dp[l-1] < dp[l]$ for all $i = 1 \dots n$ .
When processing $a_i$ we update at most one element in $dp$ , since there can be only one $dp[l]$ for which $dp[l-1] < a[i] < dp[l]$ holds.

Based on these observations, we can find such a $dp[l]$ using binary search. We want to find the first element in $dp$ that is strictly greater than $a_i$ . This takes no more than $O(\log N)$ , thus we get total complexity $O(N \log N)$ .

Optimized implementation

[BONUS] Optimized solution using data structures $O(N \log N)$

Let’s return to the first $dp$ state that we used to solve this problem.

dp[i] = \max\left(1, \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(dp[j] + 1\right)\right)

And let’s define a new array $t[]$ such that $t[a[i]] = dp[i]$ .

Now, to compute $dp[i]$ , we need to find the maximum value in the prefix of the array $t[]$ :

dp[i] = \max\left(t[0 \dots a[i] - 1] + 1\right)

This can easily be done using Segment Trees/Fenwick Trees.

Constraints

If the input numbers $a[i]$ are large, then we will have to use some tricks such as coordinate compression or using a dynamic segment tree.
This takes longer to implement than the binary search solution, and has worse memory usage (needed for the trees).

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> dp(n+1, INF);
    dp[0] = -INF;

    for (int i = 0; i < n; i++) {
        for (int l = 1; l <= n; l++) {
            if (dp[l - 1] < a[i] && a[i] < dp[l])
                dp[l] = a[i];
        }
    }

    int ans = 1;
    for (int l = 1; l <= n; l++) {
        if (d[l] < INF)
            ans = l;
    }
    return ans;
}

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> d(n + 1, INF);
    dp[0] = -INF;

    for (int i = 0; i < n; i++) {
        int l = upper_bound(dp.begin(), dp.end(), a[i]) - d.begin();
        if (dp[l - 1] < a[i] && a[i] < dp[l])
            dp[l] = a[i];
    }

    int ans = 0;
    for (int l = 0; l <= n; l++) {
        if (dp[l] < INF)
            ans = l;
    }
    return ans;
}