LCS on Permutations

Solución lenta

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

Solución eficiente

En la solución $\mathcal O(N^2)$ , incrementamos el arreglo de DP solo si $a[i] = b[j]$ , pero como ambos arreglos son permutaciones de longitud $N$ , para cada $a[i]$ debe haber solo un elemento coincidente en $b$ .

Creemos un arreglo $pos$ donde $pos[x]$ es el índice de $x$ en $a$ ( $a[pos[x]] = x$ ). Luego, podemos crear otro arreglo, $c$ , donde $c[i]$ guarda $pos[b[i]]$ .

Nótese que cada subsecuencia creciente $x_{1 \dots k}$ en $c$ corresponde a una subsecuencia común entre $a$ y $b$ . La subsecuencia creciente $c[x_1], c[x_2], \dots c[x_k]$ corresponde a la subsecuencia común $b[x_1], b[x_2], \dots b[x_k]$ , que es equivalente a $a[c[x_1]], a[c[x_2]], \dots a[c[x_k]]$ . Así, la longitud de la subsecuencia común más larga entre $a$ y $b$ es la subsecuencia creciente más larga de $c$ .

Implementación

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

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 5;
int n, a[N], b[N], c[N], pos[N];
vector<int> lis;
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		// pos is the inverse of a
		pos[a[i]] = i;
	}
	for (int i = 1; i <= n; ++i) { cin >> b[i]; }
	for (int i = 1; i <= n; ++i) { c[i] = pos[b[i]]; }
 
	for (int i = 1; i <= n; ++i) {
		int p = lower_bound(begin(lis), end(lis), c[i]) - begin(lis);
		if (p == lis.size()) lis.push_back(c[i]);
		else lis[p] = c[i];
	}
	cout << lis.size() << '\n';
}


import java.io.*;
import java.util.*;
 
public class Main {
	// CodeSnip{Kattio}
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int n = io.nextInt();
		int[] a = new int[n + 1], b = new int[n + 1], c = new int[n + 1],
		      LIS = new int[n + 1];
		int[] position = new int[n + 2];
 
		for (int i = 1; i <= n; i++) {
			a[i] = io.nextInt();
			// position is the inverse of a
			position[a[i]] = i;
		}
 
		for (int i = 1; i <= n; i++) { b[i] = io.nextInt(); }
 
		for (int i = 1; i <= n; i++) { c[i] = position[b[i]]; }
 
		// Length of the LIS
		int len = 0;
		for (int i = 1; i <= n; i++) {
			// We find the value which is >= the target value using
			// Arrays.binarySearch.
			int val = Arrays.binarySearch(LIS, 0, len, c[i]);
			if (val < 0) val = Math.abs(val + 1);
			LIS[val] = c[i];
			if (val == len) len++;
		}
 
		io.println(len);
		io.close();
	}
}


from bisect import bisect_left
 
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
 
# pos is the inverse of a
pos = [0] * (n + 1)
c = [0] * n
 
for i in range(n):
	pos[a[i]] = i + 1
 
for i in range(n):
	c[i] = pos[b[i]]
 
lis = []
for i in range(n):
	p = bisect_left(lis, c[i])
	if p == len(lis):
		lis.append(c[i])
	else:
		lis[p] = c[i]
 
print(len(lis))