PrevNext
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.

Edit This Page
Resources
cp-algo

A comprehensive guide (covers almost everything here)

Focus Problem – read through this problem before continuing!

Tutorial

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

Slow Solution

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

Resources
CPH

slow solution

Let dp[i]dp[i] be the length of the longest increasing subsequence that ends on A[i]A[i]. We can then naively compute dpdp (and thus the LIS) in O(N2)\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: O(NlogN)\mathcal O(N \log N)

Let LiL_i be an array (0-indexed) where Li[j]L_i[j] is the smallest element from the first ii elements of AA with an increasing sequence of length j+1j + 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][2, 18, 7, 20, 18, 5, 18, 15, 13, 19, 9].

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

Lemma 1: LiL_i forms a strictly increasing sequence.

Proof: Assume for a contradiction that for some jj, we have Li[j1]Li[j]L_i[j - 1] \geq L_i[j]. Let a0,a1,,aja_0, a_1, \dots, a_{j} be any increasing subsequence of length j+1j + 1 ending on Li[j]L_i[j] (so aj=Li[j]a_j = L_i[j]). Notice that a0,a1,,aj1a_0, a_1, \dots, a_{j - 1} is an increasing subsequence of length jj. Thus, Li[j]L_i[j] has to be greater than Li[j1]L_i[j - 1]. From that, we can write this equation: Li[j1]aj1<aj=Li[j]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]A[i + 1] is equal to the least index jj (with 0-indexing) such that Li[j]A[i+1]L_i[j] \geq A[i + 1].

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

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

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

To find and update the described jj in O(logN)\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 module
def 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: O(NlogN)\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 dp[k]\texttt{dp}[k] be the length of the LIS of aa that ends with the element kak \in a. Our base case is obviously dp[a[0]]=1\texttt{dp}[a[0]] = 1 (we have an LIS containing only a[0]a[0], which has length 11). Since LIS exhibits optimal substructure, we transition as follows, processing ta[1n1]\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):

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

If dp\texttt{dp} is now a RMQ data structure, the change in dp[t]\texttt{dp}[t] is merely a point update, while the calculation of max0k<tdp[k]\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 dp\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 (l1,r1)(l_1, r_1) and (l2,r2)(l_2, r_2) if they intersect (assuming l1<l2l_1 < l_2)?

Since these segments are straight, notice how l1<l2    r1>r2l_1 < l_2 \implies r_1 > r_2.

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

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

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

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 AA.

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 AA is at least the size of longest non-increasing subsequence of AA.

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 AA is equal to the size of longest non-increasing subsequence of AA!

Wrong Proof 1: See cp-algo (note that this link describes partitioning AA 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)A=(3,1,2) into the non-increasing subsequences s1=(3,1)s_1=(3,1) and s2=(2)s_2=(2). Then 33 will be moved from the front of s1s_1 to the front of s2s_2 on the first step, back to s1s_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 xx of AA from left to right, add it to the increasing subsequence with last element less than xx such that the value of this last element is maximized. If no such increasing subsequence currently exists, then start a new increasing subsequence with xx.

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 fif_i denote the length of longest non-increasing subsequence ending at AiA_i. Then the AiA_i's satisfying fi=tf_i=t for a fixed tt are an increasing subsequence for each tt. So we have covered AA 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.

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!

PrevNext