Has Not Appeared
0/10

# Longest Increasing Subsequence

Authors: Michael Cao, Benjamin Qi, Andi Qu, Andrew Wang

Contributors: Dong Liu, Siyong Huang, Aryansh Shrivastava

Finding and using the longest increasing subsequence of an array.

### Prerequisites

Resources
cp-algo

A comprehensive guide (covers almost everything here)

Focus Problem – read through this problem before continuing!

## Tutorial

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

### Slow Solution

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

Resources
CPH

slow solution

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:

C++

int find_lis(vector<int> a) {	int n = a.size(), lis = 0;	vector<int> dp(n, 1);	for (int i = 0; i < n; 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;}

Java

public static int find_lis(int[] a) {	int n = a.length, lis = 0;	int[] dp = new int[n]; Arrays.fill(dp, 1);	for (int i = 0; i < n; 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;}

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$ ending on $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 an ordered set (as demonstrated in the solution for PCB).

C++

int find_lis(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!			dp.push_back(i);		else  // oh ok, at least we can make the ending element smaller			dp[pos] = i;	}	return dp.size();}

Java

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();}

Python

# list from typing moduledef find_lis(arr: List[int]) -> int:	min_endings = []	for i in arr:		pos = bisect_left(min_endings, i)  # bisect_left from the bisect module		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 binary search.

Note that the following solution assumes knowledge of a basic PURQ data structure for RMQ. 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):

$\texttt{dp}[t] = \max_{0 \leq k < t} \texttt{dp}[k] + 1.$

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.

My implementation is below:

// Code by Aryansh Shrivastava
#include <bits/stdc++.h>using namespace std;
struct RMQ {	int n; vector<int> seg;	const int ID = 0; // at minimum, the length of a subsequence is 0 (-INF won't work here for example)	void init(int n0) { n = n0; seg.assign(2 * n, ID); }	void upd(int p, int v) {

## Example - PCB

Focus Problem – read through this problem before continuing!

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

C++

#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);

Java

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

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsDP
CFEasy
Show TagsLIS
CFNormal
Old GoldNormal
Show TagsDP
LMiONormal
Show TagsDP
Baltic OIHard
Show TagsDP, Geometry
CEOIHard
Show TagsDP
JOIHard
Show TagsBinary Search, DP, LIS

The original problem statement for "Matryoshka" is in Japanese. You can find a user-translated version of the problem here.

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!