Se le da una array de números enteros, necesita encontrar la longitud de la subsecuencia creciente más larga.
Puede haber 4 enfoques para resolver el problema.
1) Fuerza bruta:
en este enfoque, intentamos encontrar todas las subsecuencias crecientes y luego devolver la longitud máxima de la subsecuencia creciente más larga. Para hacer esto, hacemos uso de una función recursiva que devuelve la longitud del LIS posible desde el elemento actual en adelante.
Complejidad de tiempo:
Complejidad de espacio:
2) Programación dinámica
Este enfoque se basa en el hecho de que LIS hasta el i-ésimo índice es independiente de los elementos posteriores (n-i+1). Además, el LIS hasta el (i+1) elemento se puede calcular comprobando el LIS obtenido del índice 0 a i.
Enfoque de programación dinámica
Complejidad de tiempo:
Complejidad de espacio:
3) Uso de la búsqueda binaria
Los elementos se almacenan en orden creciente en la array DP donde el índice se determina mediante la búsqueda binaria. La longitud de la array da la longitud del LIS.
Complejidad de tiempo: Complejidad
de espacio:
consulte Construcción de la subsecuencia creciente más larga (N log N) para obtener más detalles.
4) Uso del árbol de segmentos
Primero, los elementos se clasifican en orden creciente conservando sus índices originales. Para LIS estrictamente creciente, para elementos iguales, el elemento con un índice más alto obtiene un lugar temprano que el más bajo. Esto se puede almacenar en una array de pares.
Ahora, se rellenan en el árbol de segmentos. Según su posición en su array ordenada, se rellenan en el árbol de segmentos en las hojas correspondientes a sus índices originales.
Inicialmente, el árbol de segmentos se inicializó con ceros. Ahora, supongamos que hemos procesado un elemento en la array ordenada. En la (i+1)ésima iteración, sea j la posición original del valor.
Luego, llenará la hoja j-ésima en el árbol de segmentos cuyo valor será el valor máximo de las hojas entre 0 a (j-1) +1.
(Longitud del LIS formado por los elementos menores que él en el subarreglo que lo precede y +1 por su inclusión)
Arr[] = {5, 1, 3, 9} Indices : {0, 1, 2, 3}
Sorted_Arr [] = {1, 3, 5, 9} Índices_originales: {1, 2, 0, 3} Índices: {0, 1, 2, 3}
C++
// Finding the Longest Increasing Subsequence using // Segment Tree #include <bits/stdc++.h> using namespace std; // function to compare two pairs int compare(pair<int, int> p1, pair<int, int> p2) { /* For same values, element with the higher index appear earlier in the sorted array. This is for strictly increasing subsequence. For increasing subsequence, the lower index appears earlier in the sorted array. */ if (p1.first == p2.first) return p1.second > p2.second; // Sorting the array according to their values. return p1.first < p2.first; } // Building the entire Segment tree, the root of which // contains the length of the LIS void buildTree(int* tree, int pos, int low, int high, int index, int value) { // index is the original index of current element // If the index is not present in the given range, // then simply return if (index < low || index > high) return; // If low == high then the current position should // be updated to the value if (low == high) { tree[pos] = value; return; } int mid = (high + low) / 2; // Recursively call the function on the // child nodes buildTree(tree, 2 * pos + 1, low, mid, index, value); buildTree(tree, 2 * pos + 2, mid + 1, high, index, value); // Assign the current position the max of the 2 child // nodes tree[pos] = max(tree[2 * pos + 1], tree[2 * pos + 2]); } // Function to query the Segment tree and return the // value for a given range int findMax(int* tree, int pos, int low, int high, int start, int end) { // Query: Same as the query function of Segment tree // If the current range is totally inside the query // range, return the value of current position if (low >= start && high <= end) return tree[pos]; // If it is out of bound, return the minimum which // would be 0 in this case if (start > high || end < low) return 0; // Partial overlap int mid = (high + low) / 2; // Call findMax on child nodes recursively and // return the maximum of the two return max(findMax(tree, 2 * pos + 1, low, mid, start, end), findMax(tree, 2 * pos + 2, mid + 1, high, start, end)); } int findLIS(int arr[], int n) { // The array of pairs stores the integers and // indices in p[i] pair<int, int> p[n]; for (int i = 0; i < n; i++) { p[i].first = arr[i]; p[i].second = i; } // Sorting the array in increasing order // of the elements sort(p, p + n, compare); // Calculating the length of the segment-tree int len = pow(2, (int)(ceil(sqrt(n))) + 1) - 1; int tree[len]; // Initializing the tree with zeroes memset(tree, 0, sizeof(tree)); // Building the segment-tree, the root node of // which contains the length of LIS for the n // elements for (int i = 0; i < n; i++) { buildTree(tree, 0, 0, n - 1, p[i].second, findMax(tree, 0, 0, n - 1, 0, p[i].second) + 1); } return tree[0]; } // Driver code int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Length of the LIS: " << findLIS(arr, n); return 0; }
Java
// Finding the Longest Increasing Subsequence // using Segment Tree import java.io.*; import java.util.*; class Pair { int first; int second; } class GFG{ // Building the entire Segment tree, the root of which // contains the length of the LIS static void buildTree(int[] tree, int pos, int low, int high, int index, int value) { // Index is the original index of current element // If the index is not present in the given range, // then simply return if (index < low || index > high) return; // If low == high then the current position // should be updated to the value if (low == high) { tree[pos] = value; return; } int mid = (high + low) / 2; // Recursively call the function on the // child nodes buildTree(tree, 2 * pos + 1, low, mid, index, value); buildTree(tree, 2 * pos + 2, mid + 1, high, index, value); // Assign the current position the max of // the 2 child nodes tree[pos] = Math.max(tree[2 * pos + 1], tree[2 * pos + 2]); } // Function to query the Segment tree and // return the value for a given range static int findMax(int[] tree, int pos, int low, int high, int start, int end) { // Query: Same as the query function of Segment // tree. If the current range is totally inside // the query range, return the value of current // position if (low >= start && high <= end) return tree[pos]; // If it is out of bound, return the minimum // which would be 0 in this case if (start > high || end < low) return 0; // Partial overlap int mid = (high + low) / 2; // Call findMax on child nodes recursively // and return the maximum of the two return Math.max(findMax(tree, 2 * pos + 1, low, mid, start, end), findMax(tree, 2 * pos + 2, mid + 1, high, start, end)); } static int findLIS(int arr[], int n) { // The array of pairs stores the integers // and indices in p[i] List<Pair> p = new ArrayList<Pair>(); for(int i = 0; i < n; i++) { Pair p1 = new Pair(); p1.first = arr[i]; p1.second = i; p.add(p1); } // Sorting the array in increasing order // of the elements Collections.sort(p, (p1, p2) -> { /* For same values, element with the higher index appear earlier in the sorted array. This is for strictly increasing subsequence. For increasing subsequence, the lower index appears earlier in the sorted array. */ if (p1.first == p2.first) return p2.second - p1.second; // Sorting the array according to their values. return p1.first - p2.first; }); // Calculating the length of the segment-tree int len = (int)(Math.pow( 2, (int)(Math.ceil(Math.sqrt(n))) + 1)) - 1; int[] tree = new int[len]; // Building the segment-tree, the root node of // which contains the length of LIS for the n // elements for(int i = 0; i < n; i++) { buildTree(tree, 0, 0, n - 1, p.get(i).second, findMax(tree, 0, 0, n - 1, 0, p.get(i).second) + 1); } return tree[0]; } // Driver Code public static void main(String[] args) { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.length; System.out.println("Length of the LIS: " + findLIS(arr, n)); } } // This code is contributed by jithin
Length of the LIS: 5
Complejidad del tiempo:
Complejidad espacial:
Tema relacionado: Árbol de segmentos
Este artículo es una contribución de Pritam Pathak . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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