Subsecuencia creciente más larga

Tutorial

En este tutorial, sea $A$ el arreglo para el que queremos hallar la LIS.

Solución lenta

Complejidad temporal: $\mathcal O(N^2)$

Sea $dp[i]$ la longitud de la subsecuencia creciente más larga que termina en $A[i]$. Entonces podemos calcular $dp$ de forma naive (y así la LIS) en tiempo $\mathcal{O}(N^2)$:

#include <vector>
using namespace std;
 
int find_lis(const vector<int> &a) {
	int lis = 0;
	vector<int> dp(a.size(), 1);
	for (int i = 0; i < a.size(); 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 findLis(int[] a) {
	int lis = 0;
	int[] dp = new int[a.length];
	Arrays.fill(dp, 1);
	for (int i = 0; i < a.length; 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;
}

from typing import List
 
 
def find_lis(a: List[int]) -> int:
	lis = 0
	dp = [1] * len(a)
	for i in range(len(a)):
		for j in range(i):
			if a[j] < a[i]:
				dp[i] = max(dp[i], dp[j] + 1)
		lis = max(lis, dp[i])
	return lis

¡Podemos hacerlo mucho mejor que esto!

Solución rápida

Complejidad temporal: $\mathcal O(N \log N)$

Sea $L_i$ un arreglo (indexado desde cero) donde $L_i[j]$ es el menor elemento entre los primeros $i$ elementos de $A$ sobre el que termina una secuencia creciente de longitud $j + 1$ (o $\infty$ si no existe tal elemento).

Por ejemplo, sea nuestro arreglo $[2, 18, 7, 20, 18, 5, 18, 15, 13, 19, 9]$.

En este caso, $L_8$ sería $[2, 5, 15]$. Algunas secuencias de ejemplo que satisfacen esto son $[2]$, $[2, 5]$ y $[2, 5, 15]$.

Lema 1: $L_i$ forma una secuencia estrictamente creciente.

Demostración: Supongamos por contradicción que para algún $j$ se tiene $L_i[j - 1] \geq L_i[j]$. Sean $a_0, a_1, \dots, a_{j}$ una subsecuencia creciente cualquiera de longitud $j + 1$ que termina en $L_i[j]$ (así $a_j = L_i[j]$). Nótese que $a_0, a_1, \dots, a_{j - 1}$ es una subsecuencia creciente de longitud $j$. Por lo tanto, $L_i[j]$ tiene que ser mayor que $L_i[j - 1]$. A partir de eso, podemos escribir esta ecuación: $L_i[j - 1] \leq a_{j-1} < a_j = L_i[j]$, que es exactamente lo que queríamos.

Lema 2: La longitud de la LIS que termina en $A[i + 1]$ es igual al menor índice $j$ (con indexación desde cero) tal que $L_i[j] \geq A[i + 1]$.

Demostración: Sea $j$ como en el enunciado. Ante todo, como $A[i + 1] > L_i[j - 1]$, existe una secuencia creciente de longitud $j+1$ que termina en $A[i + 1]$, ya que podemos anexar $A[i + 1]$ al final de la secuencia de longitud $j$. Por el Lema 1, $L_i$ es estrictamente creciente, así que $L_i[k] \geq A[i + 1]$ para todo $k \geq j$. Esto significa que no puede haber una LIS que termine en $A[i + 1]$ más larga que $j + 1$.

Lema 3: A lo sumo 1 elemento difiere entre $L_i$ y $L_{i + 1}$.

Demostración: Sea $j$ como en el Lema 2. Hay que asignar $L_{i + 1}[j]$ igual a $A[i + 1]$ porque $A[i + 1] \leq L_i[j]$. $L_{i + 1}[k] = L_i[k]$ para todo $k \neq j$, porque $A[i + 1] > L_i[k]$ para todo $k < j$ y no hay secuencias crecientes que terminen en $A[i + 1]$ para $k > j$.

Para hallar y actualizar el $j$ descrito en tiempo $\mathcal{O}(\log N)$, podemos usar una lista con búsqueda binaria, o un conjunto ordenado (como se muestra en la solución de PCB).

#include <algorithm>
#include <vector>
using namespace std;
 
int find_lis(const 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()) {
			// we can have a new, longer increasing subsequence!
			dp.push_back(i);
		} else {
			// oh ok, at least we can make the ending element smaller
			dp[pos] = i;
		}
	}
	return dp.size();
}

public static int findLis(int[] a) {
	ArrayList<Integer> dp = new ArrayList<Integer>();
	for (int i : a) {
		int pos = Collections.binarySearch(dp, i);
		pos = pos < 0 ? Math.abs(pos + 1) : pos;
		if (pos == dp.size()) {
			// we can have a new, longer increasing subsequence!
			dp.add(i);
		} else {
			// oh ok, at least we can make the ending element smaller
			dp.set(pos, i);
		}
	}
	return dp.size();
}

from typing import List
from bisect import bisect_left
 
 
def find_lis(arr: List[int]) -> int:
	min_endings = []
	for i in arr:
		pos = bisect_left(min_endings, i)
		if pos == len(min_endings):  # we can have a new, longer increasing subsequence!
			min_endings.append(i)
		else:  # oh ok, at least we can make the ending element smaller
			min_endings[pos] = i
	return len(min_endings)

Solución rápida (estructuras de datos para RMQ)

Complejidad temporal: $\mathcal O(N \log N)$, aunque quizá con un factor constante peor que la solución anterior.

Nótese que la siguiente solución asume conocimiento de una estructura de datos PURQ básica para RMQ (consulta de máximo en un rango). Implementaciones adecuadas incluyen un Árbol de Segmentos o un Árbol de Fenwick modificado, pero ambos se consideran en general temas de nivel Platino. Sin embargo, esta solución tiene la ventaja de ser más intuitiva si se está derivando LIS sobre la marcha.

Sea $\texttt{dp}[k]$ la longitud de la LIS de $a$ que termina con el elemento $k \in a$. El caso base es, obviamente, $\texttt{dp}[a[0]] = 1$ (tenemos una LIS que contiene solo $a[0]$, de longitud $1$). Como la LIS exhibe subestructura óptima, transicionamos como sigue, procesando $\forall t \in a[1 \dots n-1]$ de izquierda a derecha (lo cual debemos hacer para mantener la propiedad de que nuestra subsecuencia crece de forma estricta en esa dirección):

Si $\texttt{dp}$ es ahora una estructura de datos para RMQ, el cambio en $\texttt{dp}[t]$ es simplemente una actualización puntual, mientras que el cálculo de $\max\limits_{0 \leq k < t} \texttt{dp}[k]$ es una consulta de rango.

La respuesta final es simplemente un RMQ de extremo a extremo (o, de forma alternativa, se puede mantener un máximo acumulado de la respuesta en otra variable y actualizarlo con cada update). Este método de hecho nos da la libertad de procesar online siempre que los elementos sean lo bastante pequeños para usarse como índices, o si usamos una estructura más avanzada como un Árbol de Segmentos disperso. Si estamos dispuestos a procesar offline, como a menudo podemos, sin embargo, podemos evitar una técnica más avanzada: basta con reunir los elementos del arreglo y ordenarlos para comprimir coordenadas, creando $\texttt{dp}$ con esos IDs comprimidos.

La implementación es la siguiente:

#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{Range Maximum Segment Tree}
class MaxSegTree {
  private:
	int len;
	vector<int> segtree;
 
  public:
	MaxSegTree(int len) : len(len), segtree(2 * len) {}
 
	void set(int ind, int val) {
		for (segtree[ind += len] = val; ind > 1; ind >>= 1) {
			segtree[ind >> 1] = max(segtree[ind], segtree[ind ^ 1]);
		}
	}
 
	// maximum of the range [from, to)
	int range_max(int from, int to) {
		int max_ = INT32_MIN;
		for (from += len, to += len; from < to; from >>= 1, to >>= 1) {
			if ((from & 1) != 0) { max_ = max(max_, segtree[from++]); }
			if ((to & 1) != 0) { max_ = max(max_, segtree[--to]); }
		}
		return max_;
	}
};
// EndCodeSnip
 
int find_lis(vector<int> a) {
	// apply coordinate compression to all elements of the array
	vector<int> sorted(a);
	sort(sorted.begin(), sorted.end());
	int at = 0;
	map<int, int> coord_comp;
	for (int i : sorted) {
		if (!coord_comp.count(i)) { coord_comp[i] = at++; }
	}
	// cmp(i) gives the compressed version of index i
	auto cmp = [&](int i) -> int { return coord_comp[a[i]]; };
 
	MaxSegTree dp(coord_comp.size());
	dp.set(cmp(0), 1);
	for (int i = 1; i < a.size(); i++) {
		int max_prev = dp.range_max(0, cmp(i));
		if (max_prev != INT32_MIN) {
			dp.set(cmp(i), max_prev + 1);
		} else {
			dp.set(cmp(i), 1);
		}
	}
 
	return dp.range_max(0, coord_comp.size());
}

import java.util.*;
 
public class FindLis {
	public static int findLis(int[] a) {
		// apply coordinate compression to all elements of the array
		int[] sorted = a.clone();
		Arrays.sort(sorted);
		HashMap<Integer, Integer> coordComp = new HashMap<>();
		int at = 0;
		for (int i : sorted) {
			if (!coordComp.containsKey(i)) { coordComp.put(i, at++); }
		}
 
		MaxSegTree dp = new MaxSegTree(coordComp.size());
		dp.set(coordComp.get(a[0]), 1);
		for (int i = 1; i < a.length; i++) {
			int cmp = coordComp.get(a[i]);
			int maxPrev = dp.rangeMax(0, cmp);
			if (maxPrev != Integer.MIN_VALUE) {
				dp.set(cmp, dp.rangeMax(0, cmp) + 1);
			} else {
				dp.set(cmp, 1);
			}
		}
 
		return dp.rangeMax(0, coordComp.size());
	}
}
 
// BeginCodeSnip{Range Maximum Segment Tree}
class MaxSegTree {
	int len;
	int[] segtree;
 
	public MaxSegTree(int len) {
		this.len = len;
		segtree = new int[2 * len];
	}
 
	void set(int ind, int val) {
		for (segtree[ind += len] = val; ind > 1; ind >>= 1) {
			segtree[ind >> 1] = Math.max(segtree[ind], segtree[ind ^ 1]);
		}
	}
 
	// maximum of the range [from, to)
	int rangeMax(int from, int to) {
		int max = Integer.MIN_VALUE;
		for (from += len, to += len; from < to; from >>= 1, to >>= 1) {
			if ((from & 1) != 0) { max = Math.max(max, segtree[from++]); }
			if ((to & 1) != 0) { max = Math.max(max, segtree[--to]); }
		}
		return max;
	}
}
// EndCodeSnip

from typing import List
 
 
# BeginCodeSnip{Range Maximum Segment Tree}
class MaxSegTree:
	def __init__(self, len_: int):
		self.len = len_
		self.segtree = [0] * (2 * len_)
 
	def set(self, ind: int, val: int) -> None:
		ind += self.len
		self.segtree[ind] = val
		while ind > 1:
			self.segtree[ind >> 1] = max(self.segtree[ind], self.segtree[ind ^ 1])
			ind >>= 1
 
	# maximum of the range [from, to)
	def range_max(self, start: int, end: int) -> int:
		max_ = -float("inf")
		start += self.len
		end += self.len
		while start < end:
			if (start & 1) != 0:
				max_ = max(max_, self.segtree[start])
				start += 1
			if (end & 1) != 0:
				end -= 1
				max_ = max(max_, self.segtree[end])
 
			start >>= 1
			end >>= 1
		return max_
 
 
# EndCodeSnip
 
 
def find_lis(a: List[int]) -> int:
	# apply coordinate compression to all elements of the array
	sorted_ = sorted(a)
	coord_comp = {}
	at = 0
	for i in sorted_:
		if i not in coord_comp:
			coord_comp[i] = at
			at += 1
	# cmp(i) gives the compressed version of index i
	cmp = lambda i: coord_comp[a[i]]
 
	dp = MaxSegTree(len(coord_comp))
	dp.set(cmp(0), 1)
	for i in range(1, len(a)):
		max_prev = dp.range_max(0, cmp(i))
 
		if max_prev != -float("inf"):
			dp.set(cmp(i), max_prev + 1)
		else:
			dp.set(cmp(i), 1)
 
	return dp.range_max(0, len(coord_comp))

Ejemplo - PCB

Este problema nos pide hallar el número mínimo de conjuntos disjuntos de segmentos que no se intersectan. Esto parece bastante intimidante, así que parémoslo en dos partes:

• Encontrar un conjunto de segmentos que no se intersectan
• Minimizar el número de esos conjuntos

Aplicación 1 - Segmentos que no se intersectan

Primero, ¿qué podemos decir de dos segmentos $(l_1, r_1)$ y $(l_2, r_2)$ si se intersectan (asumiendo $l_1 < l_2$)?

Como estos segmentos son rectos, nótese que $l_1 < l_2 \implies r_1 > r_2$.

¡Esto significa que un conjunto de segmentos que no se intersectan satisface $l_i < l_j \implies r_i < r_j$ para todos los pares $(i, j)$!

Sea $A$ un arreglo donde $A[i] = x$ significa que el segmento con su extremo derecho en la posición $i$ tiene su extremo izquierdo en la posición $x$.

Si nos pidieran hallar el tamaño máximo de un conjunto de segmentos que no se intersectan, ¡la respuesta sería la LIS de $A$!

Aplicación 2 - Número mínimo de secuencias crecientes

Continuando desde la aplicación 1, ahora queremos hallar el número mínimo de subsecuencias crecientes necesarias para cubrir $A$.

Por suerte, hay una solución simple (aunque no tan obvia) para esto.

Lema (fácil): El número mínimo de subsecuencias crecientes necesarias para cubrir $A$ es al menos el tamaño de la subsecuencia no creciente más larga de $A$.

Demostración: Ningún par de elementos de una subsecuencia no creciente puede formar parte de la misma subsecuencia creciente.

Afirmación: ¡El número mínimo de subsecuencias crecientes necesarias para cubrir $A$ es igual al tamaño de la subsecuencia no creciente más larga de $A$!

Demostración incorrecta 1: Ver cp-algo  (nótese que ese enlace describe particionar $A$ en subsecuencias no crecientes en lugar de subsecuencias crecientes). Sin embargo, no es correcta porque el proceso de desenganchar y reenganchar podría no terminar nunca. Por ejemplo, consideremos particionar $A=(3,1,2)$ en las subsecuencias no crecientes $s_1=(3,1)$ y $s_2=(2)$. Entonces $3$ se moverá del frente de $s_1$ al frente de $s_2$ en el primer paso, de vuelta a $s_1$ en el segundo, y así sucesivamente.

Demostración incorrecta 2: Esta  es esencialmente la misma que la anterior.

Motivación: Consideremos la estrategia voraz obvia para construir la colección de subsecuencias crecientes (esencialmente ordenamiento por paciencia ). Para cada elemento $x$ de $A$ de izquierda a derecha, lo añadimos a la subsecuencia creciente cuyo último elemento es menor que $x$ de modo que el valor de ese último elemento quede maximizado. Si no existe actualmente tal subsecuencia creciente, empezamos una nueva subsecuencia creciente con $x$.

Este algoritmo realiza exactamente los mismos pasos que el algoritmo para calcular la longitud de la subsecuencia no creciente más larga, así que se sigue que devuelven el mismo resultado.

Demostración: Sea $f_i$ la longitud de la subsecuencia no creciente más larga que termina en $A_i$. Entonces los $A_i$ que satisfacen $f_i=t$ para un $t$ fijo forman una subsecuencia creciente para cada $t$. Así que hemos cubierto $A$ con (tamaño de la subsecuencia no creciente más larga) subsecuencias crecientes, listo.

¿Se ve por qué esto es equivalente al esbozo?

Demostración alternativa: Esto es solo un caso especial del teorema de Dilworth . Ver la demostración inductiva.

Código

#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);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
	sort(a, a + n, greater<pair<int, int>>());
	// finding the LIS of a reversed array = finding the LDS
	for (int i = 0; i < n; i++) {
		if (s.upper_bound(a[i].second) == s.end()) lis++;
		else s.erase(s.upper_bound(a[i].second));
		s.insert(a[i].second);
	}
	cout << lis;
}

import java.io.*;
import java.util.*;
 
class PCB {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		TreeMap<Integer, Integer> a =
		    new TreeMap<Integer, Integer>(Collections.reverseOrder());
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			a.put(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		// finding the LIS of a reversed array = finding the LDS
		int lis = 0;
		TreeSet<Integer> s = new TreeSet<Integer>();
		for (int k : a.keySet()) {
			if (s.higher(a.get(k)) == null) lis++;
			else s.remove(s.higher(a.get(k)));
			s.add(a.get(k));
		}
		System.out.println(lis);
	}
}

from bisect import bisect_left
 
n = int(input())
board = []
endpoints = []
for _ in range(n):
	l, r = map(int, input().split())
	board.append((l, r))
board.sort()
 
endpoints.append(board[0][1])
for x in range(1, n):
	v = board[x][1]
	if v < endpoints[-1]:
		endpoints.append(v)
	else:
		index = bisect_left(
			[-x for x in endpoints], -v
		)  # invert list in order to use bisect_left
		endpoints[index] = v
print(len(endpoints))

Problemas