# Longest Increasing Subsequence

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

Contributors: Dong Liu, Siyong Huang, Aryansh Shrivastava, Kevin Sheng

Finding and using the longest increasing subsequence of an array.

### Prerequisites

Resources | ||||
---|---|---|---|---|

cp-algo | A comprehensive guide (covers almost everything here) |

Focus Problem – try your best to solve 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++

#include <vector>using namespace std;int find_lis(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;}

Java

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

Python

from typing import Listdef find_lis(a: List[int]) -> int:lis = 0dp = [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$ 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 a sorted set (as demonstrated in the solution for PCB).

C++

#include <algorithm>#include <vector>using namespace std;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!

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 smallerdp.set(pos, i);}}return dp.size();}

Python

from typing import Listfrom bisect import bisect_leftdef 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 smallermin_endings[pos] = ireturn 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:

C++

#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 arrayvector<int> sorted(a);sort(sorted.begin(), sorted.end());int at = 0;

Java

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

Python

from typing import Listclass MaxSegTree:def __init__(self, len_: int):self.len = len_self.segtree = [0] * (2 * len_)def set(self, ind: int, val: int) -> None:ind += self.len

## Example - PCB

Focus Problem – try your best to solve 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());

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show TagsDP | |||

CF | Easy | ## Show TagsLIS | |||

CF | Normal | ||||

Old Gold | Normal | ## Show TagsDP | |||

LMiO | Normal | ## Show TagsDP | |||

CF | Normal | ## Show TagsBitmasks, DP | |||

Baltic OI | Hard | ## Show TagsDP, Geometry | |||

CEOI | Hard | ## Show TagsDP | |||

JOI | Hard | ## 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.

### Module Progress:

### 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!