PrevNext
Rare
 0/5

(Optional) Longest Increasing Subsequence

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

Finding and using the LIS of an array

Resources
cp-algoA 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.

O(N2)O(N^2)

Resources
CPHslow 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)O(N^2) time:

C++

1int find_lis(vector<int> a) {
2 int n = a.size(), lis = 0;
3 vector<int> dp(n, 1);
4 for (int i = 0; i < n; i++) {
5 for (int j = 0; j < i; j++)
6 if (a[j] < a[i])
7 dp[i] = max(dp[i], dp[j] + 1);
8 lis = max(lis, dp[i]);
9 }
10 return lis;

Java

1public static int find_lis(int[] a) {
2 int n = a.length, lis = 0;
3 int[] dp = new int[n]; Arrays.fill(dp, 1);
4 for (int i = 0; i < n; i++) {
5 for (int j = 0; j < i; j++)
6 if (a[j] < a[i])
7 dp[i] = Math.max(dp[i], dp[j] + 1);
8 lis = Math.max(lis, dp[i]);
9 }
10 return lis;

We can do much better than this though!

O(NlogN)O(N \log N)

Let LiL_i be an array where Li[j]L_i[j] is the smallest element from the first ii elements of AA with an increasing sequence of length jj ending on it (or \infty if there is no such element).

Lemma 1: LiL_i forms a non-decreasing sequence.

Proof: Assume for a contradiction that for some jj, we have Li[j]>Li[j+1]L_i[j] > L_i[j + 1]. However, this is impossible because an increasing sequence of length j+1j + 1 ending on some element implies that there is also an increasing sequence of length jj ending on that same sequence.

Lemma 2: The length of the LIS ending on A[i+1]A[i + 1] is equal to the least index jj such that Li[j]A[i+1]L_i[j] \geq A[i + 1].

Proof: Firstly, 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]. By Lemma 1, LiL_i is non-decreasing, so Li[k]A[i+1]L_i[k] \geq A[i + 1] for all kjk \geq j. This means that the length of the LIS is jj.

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

Proof: Obviously, we need to set Li+1[j]L_{i + 1}[j] to be A[i+1]A[i + 1] since Li[j]A[i+1]L_i[j] \geq A[i + 1]. We don't update anything else 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] of length greater than jj.

To find and update the described jj in O(logN)O(\log N) time, we can use a std::vector and std::lower_bound. Alternatively, we can use a std::set (demonstrated in the solution for PCB).

C++

1int find_lis(vector<int> a) {
2 vector<int> dp;
3 for (int i : a) {
4 int pos = lower_bound(dp.begin(), dp.end(), i) - dp.begin();
5 if (pos == dp.size()) dp.push_back(i);
6 else dp[pos] = i;
7 }
8 return dp.size();
9}

Java

1public static int find_lis(int[] a) {
2 ArrayList<Integer> dp = new ArrayList<Integer>();
3 for (int i : a) {
4 int pos = Collections.binarySearch(dp, i);
5 if(pos < 0) pos = Math.abs(pos + 1);
6 if (pos == dp.size()) dp.add(i);
7 else dp.set(pos, i);
8 }
9 return dp.size();
10}

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++

1#include <bits/stdc++.h>
2using namespace std;
3
4int lis = 0;
5pair<int, int> a[100000];
6set<int> s;
7
8int main() {
9 iostream::sync_with_stdio(false);
10 cin.tie(0);

Java

1import java.io.*;
2import java.util.*;
3
4class PCB{
5 public static void main(String[] args) throws IOException
6 {
7 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
8 int n = Integer.parseInt(br.readLine());
9 TreeMap<Integer, Integer> a = new TreeMap<Integer, Integer>(Collections.reverseOrder());
10 for(int i = 0; i < n; i++){

Problems

StatusSourceProblem NameDifficultyTagsSolution
Old GoldNormal
Show Tags

DP

External Sol
LMiONormal
Show Tags

DP

Baltic OIHard
Show Tags

DP, Geometry

Show Sketch
CEOIHard
Show Tags

DP

Module Progress:

Give Us Feedback on (Optional) Longest Increasing Subsequence!

PrevNext