Problema
A subsequence is formed by deleting zero or more elements while preserving the order of the remaining elements. Find the longest length shared by two arrays. Matching elements need not be adjacent. Return only the length, since several equally long subsequences may exist.
Implement longest_common_subsequence_length(first, second).
Input
first: The first sequence.
second: The second sequence.
Output
Return the maximum common subsequence length. If either array is empty, return 0.
Restricciones
Each array has 0…1,000 integers between −1,000,000,000 and 1,000,000,000. Duplicates are allowed.
Ejemplos
Entrada:
first = [1, 3, 2, 4]
second = [3, 1, 2, 4]
Salida esperada:
expected = 3Entrada:
std::vector<long long> first = {1, 3, 2, 4};
std::vector<long long> second = {3, 1, 2, 4};
Salida esperada:
long long expected = 3;Entrada:
long[] first = new long[] {1, 3, 2, 4};
long[] second = new long[] {3, 1, 2, 4};
Salida esperada:
long expected = 3;Explicación
Both contain [1, 2, 4] in that order, after deleting one value. The original arrays differ, so a length-four match is impossible.
Entrada:
first = [1, 2]
second = [3, 4]
Salida esperada:
expected = 0Entrada:
std::vector<long long> first = {1, 2};
std::vector<long long> second = {3, 4};
Salida esperada:
long long expected = 0;Entrada:
long[] first = new long[] {1, 2};
long[] second = new long[] {3, 4};
Salida esperada:
long expected = 0;Explicación
The arrays have no shared value, so their only common subsequence is empty.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Aquí importa el orden, no la adyacencia, así que las decisiones de saltar pesan más que la alineación directa.
Pista 2
Usa programación dinámica donde cada estado compara prefijos de los dos arrays.
Pista 3
Cuando los elementos difieren, toma lo mejor entre quitar uno de cada secuencia; los valores repetidos pueden crear muchos emparejamientos válidos.
Complejidad esperada
tiempo O(nm), espacio extra O(min(n, m))
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.