(Optional) Longest Increasing Subsequence

Tutorial

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

$\mathcal{O}(N^2)$

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:

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;

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!

$\mathcal{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]\ge 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]\ge A[i+1]$ for all $k\ge 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]\ge 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 $\mathcal{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).

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}

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

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⟹r_1>r_2$.

This means that a set of non-intersecting segments satisfies $l_i<l_j⟹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

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

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