(Optional) Longest Increasing Subsequence

Tutorial

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

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

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;

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!

$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 (or just a std::set).

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()) dp.push_back(i);
        else dp[pos] = i;
    }
    return dp.size();
}

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

Application 1 - Non-intersecting Segments

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

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 of $A$.

Luckily for us, there's a simple solution to this - the minimum number of increasing subsequences of $A$ is simply the size of the LDS (longest decreasing subsequence) of $A$!

(Try to prove this fact yourself - as a hint, assume the contrary for a contradiction.)

Code for PCB

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

import java.io.*; 
import java.util.*; 
 
class PCB{
   public static int find_lis(int[] a) {
      ArrayList<Integer> dp = new ArrayList<Integer>();
      for (int i : a) {
         int pos = Math.abs(Collections.binarySearch(dp, i));
         if (pos > dp.size()) dp.add(i);
         else dp.set(pos-1, i);

Application 3 - Number of LISes

#include <bits/stdc++.h>
using namespace std;

const int MOD = 30013;

struct Trapezoid {
    int x1, x2, y1, y2;
} traps[100001];

int n, top[200001], bottom[200001];

Problems