Skip to Content
CTRL K

LCIS

Solución: DP de LIS

Etiqueté las secuencias a y b.

Podemos llevar la longitud de la LCIS que termina en b[j] en una lista:

dp[j]=max(dp[j],dp[k]+1) for all k<j where a[i]=b[j] and b[k]<b[j]dp[j] = max(dp[j],dp[k]+1) \text{ for all } k \lt j \text{ where } a[i] = b[j] \text{ and } b[k] \lt b[j]

También podemos crear una lista de padres que guarda el índice del último número en dp[j] para cada j, lo que nos permite reconstruir la subsecuencia al final.

Recorriendo la secuencia a, intentamos agregar a cada subsecuencia en dp. Llevamos la LCIS actual que termina en elementos de b que son menores que a[i], y guardamos su índice como last para extenderla si a[i] coincide con un elemento posterior.

Para cada b[j], comprobamos si a[i] puede extender la LCIS que termina en b[j].

  • Si a[i]=b[j]a[i] = b[j], entonces la LCIS se puede extender, y hay que actualizar dp[j].

  • Si a[i]>b[j]a[i] \gt b[j], a[i] podría agregarse más adelante a la secuencia, y hay que actualizar la longitud de la LCIS.

  • Si a[i]<b[j]a[i] \lt b[j], no hacemos nada porque a[i] no puede extender la subsecuencia.

Después de eso, hallamos la longitud de la LCIS en dp y reconstruimos la secuencia.

Implementación

Complejidad temporal: O(NM)\mathcal{O}(NM)

#include <bits/stdc++.h>
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
 
	// read the 2 sequences
 
	int n, m;
 
	cin >> n;
	vector<int> a(n);
	for (int &i : a) { cin >> i; }
 
	cin >> m;
	vector<int> b(m);
	for (int &i : b) { cin >> i; }
 
	// initialize dp
 
	vector<int> dp(m, 0), parent(m, -1);
 
	// loop through a
 
	for (int i = 0; i < n; i++) {
		int current = 0;
		int last = -1;
 
		for (int j = 0; j < m; j++) {
			if (a[i] == b[j]) {
				if (current + 1 > dp[j]) {
					dp[j] = current + 1;
					parent[j] = last;
				}
			} else if (a[i] > b[j]) {
				if (dp[j] > current) {
					current = dp[j];
					last = j;
				}
			}
		}
	}
 
	// find the sequence length and the last index of the sequence
 
	int length = 0, pos = -1;
 
	for (int j = 0; j < m; j++) {
		if (dp[j] > length) {
			length = dp[j];
			pos = j;
		}
	}
 
	// reconstruct LCIS
 
	vector<int> lcis;
	while (pos != -1) {
		lcis.push_back(b[pos]);
		pos = parent[pos];
	}
	reverse(lcis.begin(), lcis.end());
 
	cout << length << endl;
	for (int x : lcis) { cout << x << ' '; }
}
import java.io.*;
import java.util.*;
 
public class LCIS {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
 
		// read n and sequence a
		int n = Integer.parseInt(read.readLine());
		int[] a = new int[n];
		st = new StringTokenizer(read.readLine());
		for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(st.nextToken()); }
 
		// read m and sequence b
		int m = Integer.parseInt(read.readLine());
		int[] b = new int[m];
		st = new StringTokenizer(read.readLine());
		for (int i = 0; i < m; i++) { b[i] = Integer.parseInt(st.nextToken()); }
 
		// initialize dp and parent arrays
		int[] dp = new int[m];
		int[] parent = new int[m];
		Arrays.fill(parent, -1);
 
		// LCIS DP
		for (int i = 0; i < n; i++) {
			int current = 0;
			int last = -1;
 
			for (int j = 0; j < m; j++) {
				if (a[i] == b[j]) {
					if (current + 1 > dp[j]) {
						dp[j] = current + 1;
						parent[j] = last;
					}
				} else if (a[i] > b[j]) {
					if (dp[j] > current) {
						current = dp[j];
						last = j;
					}
				}
			}
		}
 
		// find length and ending index
		int length = 0, pos = -1;
 
		for (int j = 0; j < m; j++) {
			if (dp[j] > length) {
				length = dp[j];
				pos = j;
			}
		}
 
		// reconstruct LCIS
		List<Integer> lcis = new ArrayList<>();
		while (pos != -1) {
			lcis.add(b[pos]);
			pos = parent[pos];
		}
		Collections.reverse(lcis);
 
		// output using StringBuilder
		System.out.println(length);
 
		StringBuilder out = new StringBuilder();
		for (int x : lcis) out.append(x).append(" ");
		System.out.println(out);
	}
}
# read input
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
 
# initialize dp and parent arrays
dp = [0] * m
parent = [-1] * m
 
# LCIS DP
for i in range(n):
	current = 0
	last = -1
 
	for j in range(m):
		if a[i] == b[j]:
			if current + 1 > dp[j]:
				dp[j] = current + 1
				parent[j] = last
		elif a[i] > b[j]:
			if dp[j] > current:
				current = dp[j]
				last = j
 
# find length and ending index
length = 0
pos = -1
for j in range(m):
	if dp[j] > length:
		length = dp[j]
		pos = j
 
# reconstruct LCIS
lcis = []
while pos != -1:
	lcis.append(b[pos])
	pos = parent[pos]
 
lcis.reverse()
 
# print output
print(length)
print(*lcis)
Fundamentos