# (Optional) Longest Increasing Subsequence

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

### Prerequisites

Finding and using the LIS of an array

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.

### $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 $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;34int lis = 0;5pair<int, int> a[100000];6set<int> s;78int main() {9 iostream::sync_with_stdio(false);10 cin.tie(0);

Java

1import java.io.*;2import java.util.*;34class PCB{5 public static void main(String[] args) throws IOException6 {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

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

Old Gold | Normal | ## Show TagsDP | External Sol | ||

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

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

CEOI | Hard | ## Show TagsDP |