En mi publicación anterior, expliqué en detalle el problema de la subsecuencia creciente más larga (LIS). Sin embargo, la publicación solo cubrió el código relacionado con el tamaño de consulta de LIS, pero no la construcción de LIS. Lo dejo como ejercicio. Si lo has solucionado, saludos. Si no, no estás solo, aquí tienes el código.
Si no has leído mi post anterior, lee aquí . Tenga en cuenta que el siguiente código imprime LIS en orden inverso. Podemos modificar el orden de impresión usando una pila (explícita o de sistema). Dejo la explicación como ejercicio (fácil).
C++
// C++ implementation to find longest increasing subsequence // in O(n Log n) time. #include <bits/stdc++.h> using namespace std; // Binary search int GetCeilIndex(int arr[], vector<int>& T, int l, int r, int key) { while (r - l > 1) { int m = l + (r - l) / 2; if (arr[T[m]] >= key) r = m; else l = m; } return r; } int LongestIncreasingSubsequence(int arr[], int n) { // Add boundary case, when array n is zero // Depend on smart pointers vector<int> tailIndices(n, 0); // Initialized with 0 vector<int> prevIndices(n, -1); // initialized with -1 int len = 1; // it will always point to empty location for (int i = 1; i < n; i++) { if (arr[i] < arr[tailIndices[0]]) { // new smallest value tailIndices[0] = i; } else if (arr[i] > arr[tailIndices[len - 1]]) { // arr[i] wants to extend largest subsequence prevIndices[i] = tailIndices[len - 1]; tailIndices[len++] = i; } else { // arr[i] wants to be a potential condidate of // future subsequence // It will replace ceil value in tailIndices int pos = GetCeilIndex(arr, tailIndices, -1, len - 1, arr[i]); prevIndices[i] = tailIndices[pos - 1]; tailIndices[pos] = i; } } cout << "LIS of given input" << endl; for (int i = tailIndices[len - 1]; i >= 0; i = prevIndices[i]) cout << arr[i] << " "; cout << endl; return len; } int main() { int arr[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 }; int n = sizeof(arr) / sizeof(arr[0]); printf("LIS size %d\n", LongestIncreasingSubsequence(arr, n)); return 0; }
Java
// Java implementation to find longest // increasing subsequence in O(n Log n) // time. import java.util.Arrays; class GFG { // Binary search static int GetCeilIndex(int arr[], int T[], int l, int r, int key) { while (r - l > 1) { int m = l + (r - l) / 2; if (arr[T[m]] >= key) r = m; else l = m; } return r; } static int LongestIncreasingSubsequence( int arr[], int n) { // Add boundary case, when array n is zero // Depend on smart pointers int tailIndices[] = new int[n]; // Initialized with 0 Arrays.fill(tailIndices, 0); int prevIndices[] = new int[n]; // initialized with -1 Arrays.fill(prevIndices, -1); // it will always point to empty // location int len = 1; for (int i = 1; i < n; i++) { if (arr[i] < arr[tailIndices[0]]) // new smallest value tailIndices[0] = i; else if (arr[i] > arr[tailIndices[len - 1]]) { // arr[i] wants to extend // largest subsequence prevIndices[i] = tailIndices[len - 1]; tailIndices[len++] = i; } else { // arr[i] wants to be a potential // condidate of future subsequence // It will replace ceil value in // tailIndices int pos = GetCeilIndex(arr, tailIndices, -1, len - 1, arr[i]); prevIndices[i] = tailIndices[pos - 1]; tailIndices[pos] = i; } } System.out.println("LIS of given input"); for (int i = tailIndices[len - 1]; i >= 0; i = prevIndices[i]) System.out.print(arr[i] + " "); System.out.println(); return len; } // Driver code public static void main(String[] args) { int arr[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 }; int n = arr.length; System.out.print("LIS size\n" + LongestIncreasingSubsequence(arr, n)); } } // This code is contributed by Anant Agarwal.
Python3
# Python implementation to # find longest increasing # subsequence # in O(n Log n) time. # Binary search def GetCeilIndex(arr, T, l, r, key): while (r - l > 1): m = l + (r - l)//2 if (arr[T[m]] >= key): r = m else: l = m return r def LongestIncreasingSubsequence(arr, n): # Add boundary case, # when array n is zero # Depend on smart pointers # Initialized with 0 tailIndices =[0 for i in range(n + 1)] # Initialized with -1 prevIndices =[-1 for i in range(n + 1)] # it will always point # to empty location len = 1 for i in range(1, n): if (arr[i] < arr[tailIndices[0]]): # new smallest value tailIndices[0] = i elif (arr[i] > arr[tailIndices[len-1]]): # arr[i] wants to extend # largest subsequence prevIndices[i] = tailIndices[len-1] tailIndices[len] = i len += 1 else: # arr[i] wants to be a # potential condidate of # future subsequence # It will replace ceil # value in tailIndices pos = GetCeilIndex(arr, tailIndices, -1, len-1, arr[i]) prevIndices[i] = tailIndices[pos-1] tailIndices[pos] = i print("LIS of given input") i = tailIndices[len-1] while(i >= 0): print(arr[i], " ", end ="") i = prevIndices[i] print() return len # driver code arr = [ 2, 5, 3, 7, 11, 8, 10, 13, 6 ] n = len(arr) print("LIS size\n", LongestIncreasingSubsequence(arr, n)) # This code is contributed # by Anant Agarwal.
C#
// C# implementation to find longest // increasing subsequence in O(n Log n) // time. using System; class GFG { // Binary search static int GetCeilIndex(int[] arr, int[] T, int l, int r, int key) { while (r - l > 1) { int m = l + (r - l) / 2; if (arr[T[m]] >= key) r = m; else l = m; } return r; } static int LongestIncreasingSubsequence( int[] arr, int n) { // Add boundary case, when array n is zero // Depend on smart pointers int[] tailIndices = new int[n]; // Initialized with 0 for (int i = 0; i < n; i++) tailIndices[i] = 0; int[] prevIndices = new int[n]; // initialized with -1 for (int i = 0; i < n; i++) prevIndices[i] = -1; // it will always point to empty // location int len = 1; for (int i = 1; i < n; i++) { if (arr[i] < arr[tailIndices[0]]) // new smallest value tailIndices[0] = i; else if (arr[i] > arr[tailIndices[len - 1]]) { // arr[i] wants to extend // largest subsequence prevIndices[i] = tailIndices[len - 1]; tailIndices[len++] = i; } else { // arr[i] wants to be a potential // condidate of future subsequence // It will replace ceil value in // tailIndices int pos = GetCeilIndex(arr, tailIndices, -1, len - 1, arr[i]); prevIndices[i] = tailIndices[pos - 1]; tailIndices[pos] = i; } } Console.Write("LIS of given input"); for (int i = tailIndices[len - 1]; i >= 0; i = prevIndices[i]) Console.Write(arr[i] + " "); Console.WriteLine(); return len; } // Driver code public static void Main() { int[] arr = { 2, 5, 3, 7, 11, 8, 10, 13, 6 }; int n = arr.Length; Console.Write("LIS size\n" + LongestIncreasingSubsequence(arr, n)); } } // This code is contributed by nitin mittal.
PHP
<?php // PHP implementation to find longest increasing // subsequence in O(n Log n) time. // Binary search function GetCeilIndex($arr, $T, $l, $r, $key) { while ($r - $l > 1) { $m = (int)($l + ($r - $l)/2); if ($arr[$T[$m]] >= $key) $r = $m; else $l = $m; } return $r; } function LongestIncreasingSubsequence($arr, $n) { // Add boundary case, when array n is zero // Depend on smart pointers $tailIndices=array_fill(0, $n+1, 0); // Initialized with 0 $prevIndices=array_fill(0, $n+1, -1); // initialized with -1 $len = 1; // it will always point to empty location for ($i = 1; $i < $n; $i++) { if ($arr[$i] < $arr[$tailIndices[0]]) { // new smallest value $tailIndices[0] = $i; } else if ($arr[$i] > $arr[$tailIndices[$len-1]]) { // arr[i] wants to extend largest subsequence $prevIndices[$i] = $tailIndices[$len-1]; $tailIndices[$len++] = $i; } else { // arr[i] wants to be a potential condidate of // future subsequence // It will replace ceil value in tailIndices $pos = GetCeilIndex($arr, $tailIndices, -1, $len-1, $arr[$i]); $prevIndices[$i] = $tailIndices[$pos-1]; $tailIndices[$pos] = $i; } } echo "LIS of given input\n"; for ($i = $tailIndices[$len-1]; $i >= 0; $i = $prevIndices[$i]) echo $arr[$i]." "; echo "\n"; return $len; } // Driver code $arr = array( 2, 5, 3, 7, 11, 8, 10, 13, 6 ); $n = count($arr); print("LIS size ".LongestIncreasingSubsequence($arr, $n)); // This code is contributed by chandan_jnu ?>
Javascript
<script> // JavaScript implementation to find longest // increasing subsequence in O(n Log n) time. // Binary search function GetCeilIndex(arr, T, l, r, key) { while (r - l > 1) { let m = l + parseInt((r - l) / 2, 10); if (arr[T[m]] >= key) r = m; else l = m; } return r; } function LongestIncreasingSubsequence(arr, n) { // Add boundary case, when array n is zero // Depend on smart pointers let tailIndices = new Array(n); // Initialized with 0 for (let i = 0; i < n; i++) tailIndices[i] = 0; let prevIndices = new Array(n); // initialized with -1 for (let i = 0; i < n; i++) prevIndices[i] = -1; // it will always point to empty // location let len = 1; for (let i = 1; i < n; i++) { if (arr[i] < arr[tailIndices[0]]) // new smallest value tailIndices[0] = i; else if (arr[i] > arr[tailIndices[len - 1]]) { // arr[i] wants to extend // largest subsequence prevIndices[i] = tailIndices[len - 1]; tailIndices[len++] = i; } else { // arr[i] wants to be a potential // condidate of future subsequence // It will replace ceil value in // tailIndices let pos = GetCeilIndex(arr, tailIndices, -1, len - 1, arr[i]); prevIndices[i] = tailIndices[pos - 1]; tailIndices[pos] = i; } } document.write("LIS of given input" + "</br>"); for (let i = tailIndices[len - 1]; i >= 0; i = prevIndices[i]) document.write(arr[i] + " "); document.write("</br>"); return len; } let arr = [ 2, 5, 3, 7, 11, 8, 10, 13, 6 ]; let n = arr.length; document.write("LIS size " + LongestIncreasingSubsequence(arr, n)); </script>
LIS of given input 13 10 8 7 3 2 LIS size 6
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)
Ejercicios:
- Conoces el algoritmo de Kadane para encontrar el subarreglo de suma máxima . Modifique el algoritmo de Kadane para rastrear la ubicación inicial y final del subarreglo de suma máxima.
- Modifique el algoritmo de Kadane para encontrar el subarreglo de suma máxima en un arreglo circular. Consulte el foro GFG para obtener muchos comentarios sobre la pregunta.
- Dados dos enteros A y B como entrada. Encuentre la cantidad de números de Fibonacci que existen entre estos dos números (incluidos A y B). Por ejemplo, A = 3 y B = 18, hay 4 números de Fibonacci entre {3, 5, 8, 13}. Hágalo en tiempo O (log K), donde K es max (A, B). ¿Cuál es tu observación?
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA