Dada una array de n enteros positivos. Necesitamos encontrar la mayor secuencia creciente de enteros positivos consecutivos.
Ejemplos:
Input : arr[] = {5, 7, 6, 7, 8} Output : Size of LIS = 4 LIS = 5, 6, 7, 8 Input : arr[] = {5, 7, 8, 7, 5} Output : Size of LIS = 2 LIS = 7, 8
Este problema se puede resolver fácilmente mediante el concepto de LIS , donde cada siguiente elemento mayor difiere del anterior en 1. Pero esto requerirá una complejidad de tiempo O (n ^ 2).
Con el uso de hashing podemos encontrar el tamaño de la secuencia creciente más larga con enteros consecutivos en complejidad temporal de O(n).
Creamos una tabla hash. Ahora, para cada elemento arr[i], realizamos hash[arr[i]] = hash[arr[i] – 1] + 1. Entonces, para cada elemento conocemos el final de subsecuencia creciente consecutivo más largo con eso. Finalmente devolvemos el valor máximo de la tabla hash.
Implementación:
C++
// C++ implementation of longest continuous increasing // subsequence #include <bits/stdc++.h> using namespace std; // Function for LIS int findLIS(int A[], int n) { unordered_map<int, int> hash; // Initialize result int LIS_size = 1; int LIS_index = 0; hash[A[0]] = 1; // iterate through array and find // end index of LIS and its Size for (int i = 1; i < n; i++) { hash[A[i]] = hash[A[i] - 1] + 1; if (LIS_size < hash[A[i]]) { LIS_size = hash[A[i]]; LIS_index = A[i]; } } // print LIS size cout << "LIS_size = " << LIS_size << "\n"; // print LIS after setting start element cout << "LIS : "; int start = LIS_index - LIS_size + 1; while (start <= LIS_index) { cout << start << " "; start++; } } // driver int main() { int A[] = { 2, 5, 3, 7, 4, 8, 5, 13, 6 }; int n = sizeof(A) / sizeof(A[0]); findLIS(A, n); return 0; }
Java
// Java implementation of longest continuous increasing // subsequence import java.util.*; class GFG { // Function for LIS static void findLIS(int A[], int n) { Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); // Initialize result int LIS_size = 1; int LIS_index = 0; hash.put(A[0], 1); // iterate through array and find // end index of LIS and its Size for (int i = 1; i < n; i++) { hash.put(A[i], hash.get(A[i] - 1)==null? 1:hash.get(A[i] - 1)+1); if (LIS_size < hash.get(A[i])) { LIS_size = hash.get(A[i]); LIS_index = A[i]; } } // print LIS size System.out.println("LIS_size = " + LIS_size); // print LIS after setting start element System.out.print("LIS : "); int start = LIS_index - LIS_size + 1; while (start <= LIS_index) { System.out.print(start + " "); start++; } } // Driver code public static void main(String[] args) { int A[] = { 2, 5, 3, 7, 4, 8, 5, 13, 6 }; int n = A.length; findLIS(A, n); } } // This code is contributed by Princi Singh
Python3
# Python3 implementation of longest # continuous increasing subsequence # Function for LIS def findLIS(A, n): hash = dict() # Initialize result LIS_size, LIS_index = 1, 0 hash[A[0]] = 1 # iterate through array and find # end index of LIS and its Size for i in range(1, n): # If the desired key is not present # in dictionary, it will throw key error, # to avoid this error this is necessary if A[i] - 1 not in hash: hash[A[i] - 1] = 0 hash[A[i]] = hash[A[i] - 1] + 1 if LIS_size < hash[A[i]]: LIS_size = hash[A[i]] LIS_index = A[i] # print LIS size print("LIS_size =", LIS_size) # print LIS after setting start element print("LIS : ", end = "") start = LIS_index - LIS_size + 1 while start <= LIS_index: print(start, end = " ") start += 1 # Driver Code if __name__ == "__main__": A = [ 2, 5, 3, 7, 4, 8, 5, 13, 6 ] n = len(A) findLIS(A, n) # This code is contributed by sanjeev2552
C#
// C# implementation of longest continuous increasing // subsequence using System; using System.Collections.Generic; class GFG { // Function for LIS static void findLIS(int []A, int n) { Dictionary<int,int> hash = new Dictionary<int,int>(); // Initialize result int LIS_size = 1; int LIS_index = 0; hash.Add(A[0], 1); // iterate through array and find // end index of LIS and its Size for (int i = 1; i < n; i++) { if(hash.ContainsKey(A[i]-1)) { var val = hash[A[i]-1]; hash.Remove(A[i]); hash.Add(A[i], val + 1); } else { hash.Add(A[i], 1); } if (LIS_size < hash[A[i]]) { LIS_size = hash[A[i]]; LIS_index = A[i]; } } // print LIS size Console.WriteLine("LIS_size = " + LIS_size); // print LIS after setting start element Console.Write("LIS : "); int start = LIS_index - LIS_size + 1; while (start <= LIS_index) { Console.Write(start + " "); start++; } } // Driver code public static void Main(String[] args) { int []A = { 2, 5, 3, 7, 4, 8, 5, 13, 6 }; int n = A.Length; findLIS(A, n); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript implementation of longest continuous increasing // subsequence // Function for LIS function findLIS(A, n) { let hash = new Map(); // Initialize result let LIS_size = 1; let LIS_index = 0; hash.set(A[0], 1); // iterate through array and find // end index of LIS and its Size for (let i = 1; i < n; i++) { hash.set(A[i], hash.get(A[i] - 1) == null ? 1 : hash.get(A[i] - 1) + 1); if (LIS_size < hash.get(A[i])) { LIS_size = hash.get(A[i]); LIS_index = A[i]; } } // print LIS size document.write("LIS_size = " + LIS_size + "<br>"); // print LIS after setting start element document.write("LIS : "); let start = LIS_index - LIS_size + 1; while (start <= LIS_index) { document.write(start + " "); start++; } } // Driver code let A = [2, 5, 3, 7, 4, 8, 5, 13, 6]; let n = A.length; findLIS(A, n); // This code is contributed by gfgking </script>
LIS_size = 5 LIS : 2 3 4 5 6
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA