LIS utilizando el árbol de segmentos

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} 
 

// 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;
}

// 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.