Rare
0/5

# (Optional) Longest Increasing Subsequence

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

### Prerequisites

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 $A$ be the array we want to find the LIS for.

### $O(N^2)$

Resources
CPHslow 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 $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(N \log N)$

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

Lemma 1: $L_i$ forms a non-decreasing sequence.

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

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

Proof: Firstly, since $A[i + 1] > L_i[j - 1]$, there is an increasing sequence of length $j$ ending on $A[i + 1]$. By Lemma 1, $L_i$ is non-decreasing, so $L_i[k] \geq A[i + 1]$ for all $k \geq j$. This means that the length of the LIS is $j$.

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

Proof: Obviously, we need to set $L_{i + 1}[j]$ to be $A[i + 1]$ since $L_i[j] \geq A[i + 1]$. We don't update anything else though, since $A[i + 1] > L_i[k]$ for all $k < j$ and there are no increasing sequences ending on $A[i + 1]$ of length greater than $j$.

To find and update the described $j$ in $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 $(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++

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