Longest Increasing Subsequence

Tutorial

In this tutorial, let $A$ be the array we want to find the LIS for.

Slow Solution

Time Complexity: $\mathcal O(N^2)$

Let $dp[i]$ be the length of the longest increasing subsequence that ends on $A[i]$. We can then naively compute $dp$ (and thus the LIS) in $\mathcal{O}(N^2)$ time:

Copy
#include <vector>
using namespace std;

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

Copy
public static int findLis(int[] a) {
	int lis = 0;
	int[] dp = new int[a.length];
	Arrays.fill(dp, 1);
	for (int i = 0; i < a.length; i++) {
		for (int j = 0; j < i; j++) {
			if (a[j] < a[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); }
		}
		lis = Math.max(lis, dp[i]);
	}
	return lis;
}

Copy
from typing import List


def find_lis(a: List[int]) -> int:
	lis = 0
	dp = [1] * len(a)
	for i in range(len(a)):
		for j in range(i):
			if a[j] < a[i]:
				dp[i] = max(dp[i], dp[j] + 1)
		lis = max(lis, dp[i])
	return lis

We can do much better than this though!

Fast Solution

Time Complexity: $\mathcal O(N \log N)$

Let $L_i$ be an array (0-indexed) where $L_i[j]$ is the smallest element from the first $i$ elements of $A$ with an increasing sequence of length $j + 1$ ending on it (or $\infty$ if there is no such element).

For example, let our array be $[2, 18, 7, 20, 18, 5, 18, 15, 13, 19, 9]$.

In this case, $L_8$ would be $[2, 5, 15]$. Some example sequences satisfying these are $[2]$, $[2, 5]$, and $[2, 5, 15]$.

Lemma 1: $L_i$ forms a strictly increasing sequence.

Proof: Assume for a contradiction that for some $j$, we have $L_i[j - 1] \geq L_i[j]$. Let $a_0, a_1, \dots, a_{j}$ be any increasing subsequence of length $j + 1$ ending on $L_i[j]$ (so $a_j = L_i[j]$). Notice that $a_0, a_1, \dots, a_{j - 1}$ is an increasing subsequence of length $j$. Thus, $L_i[j]$ has to be greater than $L_i[j - 1]$. From that, we can write this equation: $L_i[j - 1] \leq a_{j-1} < a_j = L_i[j]$, which is exactly what we wanted.

Lemma 2: The length of the LIS ending on $A[i + 1]$ is equal to the least index $j$ (with 0-indexing) such that $L_i[j] \geq A[i + 1]$.

Proof: Let $j$ be defined as it is in the statement. First of all, since $A[i + 1] > L_i[j - 1]$, there is an increasing sequence of length $j+1$ ending at $A[i + 1]$, as we can append $A[i + 1]$ to the end of the sequence of length $j$. By Lemma 1, $L_i$ is strictly increasing, so $L_i[k] \geq A[i + 1]$ for all $k \geq j$. This means that there cannot be a LIS ending at $A[i + 1]$ longer than $j + 1$.

Lemma 3: At most 1 element differs between $L_i$ and $L_{i + 1}$.

Proof: Let $j$ be defined as it was in Lemma 2. We need to set $L_{i + 1}[j]$ to be $A[i + 1]$ since $A[i + 1] \leq L_i[j]$. $L_{i + 1}[k] = L_i[k]$ for all $k \neq j$, though, since $A[i + 1] > L_i[k]$ for all $k < j$ and there are no increasing sequences ending on $A[i + 1]$ for $k > j$.

To find and update the described $j$ in $\mathcal{O}(\log N)$ time, we can use a list with binary search, or we can use a sorted set (as demonstrated in the solution for PCB).

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

int find_lis(const vector<int> &a) {
	vector<int> dp;
	for (int i : a) {
		int pos = lower_bound(dp.begin(), dp.end(), i) - dp.begin();
		if (pos == dp.size()) {
			// we can have a new, longer increasing subsequence!

Copy
public static int findLis(int[] a) {
	ArrayList<Integer> dp = new ArrayList<Integer>();
	for (int i : a) {
		int pos = Collections.binarySearch(dp, i);
		pos = pos < 0 ? Math.abs(pos + 1) : pos;
		if (pos == dp.size()) {
			// we can have a new, longer increasing subsequence!
			dp.add(i);
		} else {
			// oh ok, at least we can make the ending element smaller
			dp.set(pos, i);
		}
	}
	return dp.size();
}

Copy
from typing import List
from bisect import bisect_left


def find_lis(arr: List[int]) -> int:
	min_endings = []
	for i in arr:
		pos = bisect_left(min_endings, i)
		if pos == len(min_endings):  # we can have a new, longer increasing subsequence!
			min_endings.append(i)
		else:  # oh ok, at least we can make the ending element smaller
			min_endings[pos] = i
	return len(min_endings)

Fast Solution (RMQ Data Structures)

Time Complexity: $\mathcal O(N \log N)$, but perhaps a constant factor slower than the previous solution.

Note that the following solution assumes knowledge of a basic PURQ data structure for RMQ (range max query). Suitable implementations include a segment tree or a modified Fenwick tree, but both of these are generally considered Platinum level topics. However, this solution has the advantage of being more intuitive if you're deriving LIS on the spot.

Let $\texttt{dp}[k]$ be the length of the LIS of $a$ that ends with the element $k \in a$. Our base case is obviously $\texttt{dp}[a[0]] = 1$ (we have an LIS containing only $a[0]$, which has length $1$). Since LIS exhibits optimal substructure, we transition as follows, processing $\forall t \in a[1 \dots n-1]$ from left to right (which we must do in order to maintain the property that our subsequence strictly increases in this direction):

If $\texttt{dp}$ is now a RMQ data structure, the change in $\texttt{dp}[t]$ is merely a point update, while the calculation of $\max\limits_{0 \leq k < t} \texttt{dp}[k]$ is a range query.

Our final answer is just an RMQ from end to end (or, alternatively, you could keep a running max of the answer in another variable and change it with each update). This method actually gives us the leisure to process online as long as our elements are small enough to be used as indices, or if we use a more advanced data structure such as a sparse segment tree. If we are willing to process offline as we often can, however, we can avoid using a more advanced technique: it suffices to collect the array elements and sort them to coordinate compress, creating $\texttt{dp}$ with those compressed IDs instead.

The implementation follows:

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

 Code Snippet: Range Maximum Segment Tree (Click to expand)

int find_lis(vector<int> a) {
	// apply coordinate compression to all elements of the array
	vector<int> sorted(a);
	sort(sorted.begin(), sorted.end());
	int at = 0;

Copy
import java.util.*;

public class FindLis {
	public static int findLis(int[] a) {
		// apply coordinate compression to all elements of the array
		int[] sorted = a.clone();
		Arrays.sort(sorted);
		HashMap<Integer, Integer> coordComp = new HashMap<>();
		int at = 0;
		for (int i : sorted) {

Copy
from typing import List


 Code Snippet: Range Maximum Segment Tree (Click to expand)


def find_lis(a: List[int]) -> int:
	# apply coordinate compression to all elements of the array
	sorted_ = sorted(a)
	coord_comp = {}

Example - PCB

This problem asks us to find the minimum number of disjoint sets of non-intersecting segments. This seems quite intimidating, so let's break it up into two parts:

• Finding a set of non-intersecting segments
• Minimizing the number of these sets

Application 1 - Non-intersecting Segments

First, what can we say about two segments $(l_1, r_1)$ and $(l_2, r_2)$ if they intersect (assuming $l_1 < l_2$)?

Since these segments are straight, notice how $l_1 < l_2 \implies r_1 > r_2$.

This means that a set of non-intersecting segments satisfies $l_i < l_j \implies r_i < r_j$ for all pairs $(i, j)$!

Let $A$ be an array where $A[i] = x$ means that the segment with its right endpoint at position $i$ has its left endpoint at position $x$.

If we were asked to find the maximum size of a set of non-intersecting segments, the answer would be the LIS of $A$!

Application 2 - Minimum Number of Increasing Sequences

Continuing from application 1, we now want to find the minimum number of increasing subsequences required to cover $A$.

Luckily for us, there's a simple (though not so obvious) solution to this.

Lemma (Easy): The minimum number of increasing subsequences required to cover $A$ is at least the size of longest non-increasing subsequence of $A$.

Proof: No two elements of any non-increasing subsequence can be part of the same increasing subsequence.

Claim: The minimum number of increasing subsequences required to cover $A$ is equal to the size of longest non-increasing subsequence of $A$!

Wrong Proof 1: See cp-algo (note that this link describes partitioning $A$ into non-increasing subsequences rather than increasing subsequences). However, it's not correct because the process of unhooking and reattaching might never terminate. For example, consider partitioning $A=(3,1,2)$ into the non-increasing subsequences $s_1=(3,1)$ and $s_2=(2)$. Then $3$ will be moved from the front of $s_1$ to the front of $s_2$ on the first step, back to $s_1$ on the second step, and so on.

Wrong Proof 2: This is essentially the same as the above.

Motivation: Consider the obvious greedy strategy to construct the collection of increasing subsequences (essentially patience sorting). For each element $x$ of $A$ from left to right, add it to the increasing subsequence with last element less than $x$ such that the value of this last element is maximized. If no such increasing subsequence currently exists, then start a new increasing subsequence with $x$.

This algorithm performs exactly the same steps as the algorithm to compute the length of the longest non-increasing subsequence, so it follows that they return the same result.

Proof: Let $f_i$ denote the length of longest non-increasing subsequence ending at $A_i$. Then the $A_i$'s satisfying $f_i=t$ for a fixed $t$ are an increasing subsequence for each $t$. So we have covered $A$ with (size of longest non-increasing subsequence) increasing subsequences, done.

Do you see why this is equivalent to the sketch?

Alternative Proof: This is just a special case of Dilworth's Theorem. See the inductive proof.

Code

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

int lis = 0;
pair<int, int> a[100000];
set<int> s;

int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);

Copy
import java.io.*;
import java.util.*;

class PCB {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		TreeMap<Integer, Integer> a =
		    new TreeMap<Integer, Integer>(Collections.reverseOrder());
		for (int i = 0; i < n; i++) {

Problems