Dadas dos arrays firstArr[] , que consisten solo en elementos distintos, y secondArr[] , la tarea es encontrar la longitud de LCS entre estas 2 arrays.
Ejemplos:
Entrada: firstArr[] = {3, 5, 1, 8}, secondArr[] = {3, 3, 5, 3, 8}
Salida: 3.
Explicación: LCS entre estas dos arrays es {3, 5, 8} .Entrada : primeraArr[] = {1, 2, 1}, segundaArr[] = {3}
Salida: 0
Enfoque ingenuo: siga los pasos a continuación para resolver el problema utilizando el enfoque más simple posible:
- Inicialice una array dp[][] tal que dp[i][j] almacene la subsecuencia común más larga de firstArr[ :i] y secondArr[ :j] .
- Recorra la array firstArr[] y para cada elemento de array de la array firstArr[] , recorra la array secondArr[] .
- Si firstArr[i] = secondArr[j]: Establecer dp[i][j] = dp[i – 1][j – 1] + 1 .
- De lo contrario: Establezca dp[i][j] = max(dp[ i – 1][j], dp[i][j – 1]) .
Complejidad temporal: O(N * M), donde N y M son los tamaños de las arrays firstArr[] y secondArr[] respectivamente.
Espacio Auxiliar: O(N * M)
Enfoque eficiente: para optimizar el enfoque anterior, siga los pasos a continuación:
- Inicialice un Map , digamos mp , para almacenar las asignaciones map[firstArr[i]] = i , es decir, asigne elementos de la primera array a sus respectivos índices.
- Dado que los elementos que están presentes en secondArr[] pero no en firstArr[] no son útiles en absoluto, ya que nunca pueden ser parte de una subsecuencia común, recorra la array secondArr[] y para cada elemento de la array, verifique si es presentes en el Mapa o no .
- Si se determina que es cierto, inserte map[ secondArr [i]] en una array temporal. De lo contrario, ignóralo.
- Encuentre la subsecuencia creciente más larga (LIS) de la array temporal obtenida e imprima su longitud como la respuesta requerida.
Ilustración:
firstArr[] = {3, 5, 1, 8}
secondArr={3, 3, 4, 5, 3, 8}
Asignación : 3->0, 5->1, 1->2, 8->3 ( De firstArr)
tempArr[] = {0, 0, 1, 0, 3}
Por lo tanto, la longitud de LIS de tempArr[] = 3 ({0, 1, 3})
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the Longest Common // Subsequence between the two arrays int LCS(vector<int>& firstArr, vector<int>& secondArr) { // Maps elements of firstArr[] // to their respective indices unordered_map<int, int> mp; // Traverse the array firstArr[] for (int i = 0; i < firstArr.size(); i++) { mp[firstArr[i]] = i + 1; } // Stores the indices of common elements // between firstArr[] and secondArr[] vector<int> tempArr; // Traverse the array secondArr[] for (int i = 0; i < secondArr.size(); i++) { // If current element exists in the Map if (mp.find(secondArr[i]) != mp.end()) { tempArr.push_back(mp[secondArr[i]]); } } // Stores lIS from tempArr[] vector<int> tail; tail.push_back(tempArr[0]); for (int i = 1; i < tempArr.size(); i++) { if (tempArr[i] > tail.back()) tail.push_back(tempArr[i]); else if (tempArr[i] < tail[0]) tail[0] = tempArr[i]; else { auto it = lower_bound(tail.begin(), tail.end(), tempArr[i]); *it = tempArr[i]; } } return (int)tail.size(); } // Driver Code int main() { vector<int> firstArr = { 3, 5, 1, 8 }; vector<int> secondArr = { 3, 3, 5, 3, 8 }; cout << LCS(firstArr, secondArr); return 0; }
Java
// Java program to to implement // the above approach import java.util.*; class GFG { // Function to find the Longest Common // Subsequence between the two arrays static int LCS(int[] firstArr,int[] secondArr) { // Maps elements of firstArr[] // to their respective indices HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); // Traverse the array firstArr[] for (int i = 0; i < firstArr.length; i++) { mp.put(firstArr[i], i + 1); } // Stores the indices of common elements // between firstArr[] and secondArr[] Vector<Integer> tempArr = new Vector<>(); // Traverse the array secondArr[] for (int i = 0; i < secondArr.length; i++) { // If current element exists in the Map if (mp.containsKey(secondArr[i])) { tempArr.add(mp.get(secondArr[i])); } } // Stores lIS from tempArr[] Vector<Integer> tail = new Vector<>(); tail.add(tempArr.get(0)); for (int i = 1; i < tempArr.size(); i++) { if (tempArr.get(i) > tail.lastElement()) tail.add(tempArr.get(i)); else if (tempArr.get(i) < tail.get(0)) tail.add(0, tempArr.get(i)); } return (int)tail.size(); } // Driver Code public static void main(String[] args) { int[] firstArr = { 3, 5, 1, 8 }; int[] secondArr = { 3, 3, 5, 3, 8 }; System.out.print(LCS(firstArr, secondArr)); } } // This code is contributed by gauravrajput1
Python3
# Python3 program to to implement # the above approach from bisect import bisect_left # Function to find the Longest Common # Subsequence between the two arrays def LCS(firstArr, secondArr): # Maps elements of firstArr[] # to their respective indices mp = {} # Traverse the array firstArr[] for i in range(len(firstArr)): mp[firstArr[i]] = i + 1 # Stores the indices of common elements # between firstArr[] and secondArr[] tempArr = [] # Traverse the array secondArr[] for i in range(len(secondArr)): # If current element exists in the Map if (secondArr[i] in mp): tempArr.append(mp[secondArr[i]]) # Stores lIS from tempArr[] tail = [] tail.append(tempArr[0]) for i in range(1, len(tempArr)): if (tempArr[i] > tail[-1]): tail.append(tempArr[i]) elif (tempArr[i] < tail[0]): tail[0] = tempArr[i] else : it = bisect_left(tail, tempArr[i]) it = tempArr[i] return len(tail) # Driver Code if __name__ == '__main__': firstArr = [3, 5, 1, 8 ] secondArr = [3, 3, 5, 3, 8 ] print (LCS(firstArr, secondArr)) # This code is contributed by mohit kumar 29
C#
// C# program to to implement // the above approach using System; using System.Collections.Generic; public class GFG { // Function to find the longest Common // Subsequence between the two arrays static int LCS(int[] firstArr,int[] secondArr) { // Maps elements of firstArr[] // to their respective indices Dictionary<int,int> mp = new Dictionary<int,int>(); // Traverse the array firstArr[] for (int i = 0; i < firstArr.Length; i++) { mp.Add(firstArr[i], i + 1); } // Stores the indices of common elements // between firstArr[] and secondArr[] List<int> tempArr = new List<int>(); // Traverse the array secondArr[] for (int i = 0; i < secondArr.Length; i++) { // If current element exists in the Map if (mp.ContainsKey(secondArr[i])) { tempArr.Add(mp[secondArr[i]]); } } // Stores lIS from tempArr[] List<int> tail = new List<int>(); tail.Add(tempArr[0]); for (int i = 1; i < tempArr.Count; i++) { if (tempArr[i] > tail[tail.Count-1]) tail.Add(tempArr[i]); else if (tempArr[i] < tail[0]) tail.Insert(0, tempArr[i]); } return (int)tail.Count; } // Driver Code public static void Main(String[] args) { int[] firstArr = { 3, 5, 1, 8 }; int[] secondArr = { 3, 3, 5, 3, 8 }; Console.Write(LCS(firstArr, secondArr)); } } // This code is contributed by Rajput-Ji.
Javascript
<script> // Javascript program to to implement // the above approach // Function to find the longest Common // Subsequence between the two arrays function LCS(firstArr, secondArr) { // Maps elements of firstArr[] // to their respective indices let mp = new Map() // Traverse the array firstArr[] for(let i = 0; i < firstArr.length; i++) { mp.set(firstArr[i], i + 1); } // Stores the indices of common elements // between firstArr[] and secondArr[] let tempArr = []; // Traverse the array secondArr[] for(let i = 0; i < secondArr.length; i++) { // If current element exists in the Map if (mp.has(secondArr[i])) { tempArr.push(mp.get(secondArr[i])); } } // Stores lIS from tempArr[] let tail = []; tail.push(tempArr[0]); for(let i = 1; i < tempArr.length; i++) { if (tempArr[i] > tail[tail.length - 1]) tail.push(tempArr[i]); else if (tempArr[i] < tail[0]) tail.unshift(0, tempArr[i]); } return tail.length; } // Driver Code let firstArr = [ 3, 5, 1, 8 ]; let secondArr = [ 3, 3, 5, 3, 8 ]; document.write(LCS(firstArr, secondArr)); // This code is contributed by gfgking </script>
3
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)