Subsecuencia creciente más larga usando BIT

Dada una array arr , la tarea es encontrar la longitud de la secuencia creciente más larga usando el árbol indexado binario (BIT) 

Ejemplos: 

Input: arr = {6, 5, 1, 3, 2, 4, 8, 7}
Output: 4
Explanation:
The possible subsequences are 
{1 2 4 7}, {1 2 4 8}, 
{1 3 4 8}, {1 3 4 7}  

Now insert the elements one by one from left to right:

6 is inserted: max length till 5 = 0, ans for 6 is 1
5 is inserted: max length till 4 = 0, ans for 5 is 1
1 is inserted: max length till 0 = 2, ans for 1 is 1
3 is inserted: max length till 2 = 1, ans for 3 is 2
2 is inserted: max length till 1 = 1, ans for 2 is 2
4 is inserted: max length till 3 = 2, ans for 4 is 3
8 is inserted: max length till 7 = 3, ans for 8 is 4
7 is inserted: max length till 6 = 3, ans for 7 is 4

Input: arr = {1, 2, 3, 4, 1, 5}
Output: 5

Requisito previo para esta publicación: árbol indexado binario  

Acercarse:  

  • Primero, use la compresión de coordenadas (reemplace todos los valores de la array por números que van del 1 al N). Esto reducirá el número máximo en la array y nos ayudará a resolver el problema anterior en tiempo NlogN. Además, esto nos ayudará a reducir la memoria.
  • Cree una nueva array BIT de longitud N + 1.
  • Ahora, recorra la array de izquierda a derecha y agregue el elemento actual al BIT.
  • Cuando se inserta el i-ésimo elemento (A[i]) en el BIT, verifique la longitud de la subsecuencia más larga que se puede formar hasta A[i] – 1. Sea este valor x. Si x + 1 es mayor que el elemento actual en BIT, actualice el BIT.

A continuación se muestra la implementación del enfoque anterior:  

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to map
// numbers using coordinate
// compression
void coordinateCompression(int arr[], int n)
{
 
    // Set will store
    // all unique numbers
    set<int> s;
    for (int i = 0; i < n; i++) {
        s.insert(arr[i]);
    }
 
    // Map will store
    // the new elements
    int index = 0;
    map<int, int> mp;
    set<int>::iterator itr;
 
    for (itr = s.begin(); itr != s.end(); itr++) {
        // For every new number in the set,
        index++;
        // Increment the index of the
        // current number and store it
        // in a hashmap. Here index
        // for every element is the
        // new value with the
        // current element is replaced
        mp[*itr] = index;
    }
    for (int i = 0; i < n; i++) {
        // now change the current element
        // to range 1 to N.
        arr[i] = mp[arr[i]];
    }
}
 
// Function to calculate
// length of maximum
// increasing sequence till
// i'th index
int query(int BIT[], int index, int n)
{
 
    int ans = 0;
    while (index > 0) {
        ans = max(ans, BIT[index]);
        // Go to parent node
        index -= index & (-index);
    }
    return ans;
}
 
// Function for updating
// BIT array for maximum
// increasing sequence till
// i'th index
void update(int BIT[], int index, int n)
{
 
    // If 4 is inserted in BIT,
    // check for maximum length
    // subsequence till element 3.
    // Let this subsequence length be x.
    // If x + 1 is greater than
    // the current element in BIT,
    // update the BIT array
    int x = query(BIT, index - 1, n);
    int value = x + 1;
    while (index <= n) {
 
        // Store maximum length subsequence length till index
        // Here index is the
        // coordinate compressed element
        BIT[index] = max(BIT[index], value);
 
        // Go to child node and update that node
        index += index & (-index);
    }
}
 
// Function to calculate
// maximum Longest Increasing
// Sequence length
int findLISLength(int arr[], int n)
{
 
    coordinateCompression(arr, n);
    int BIT[n + 1];
 
    // Initialising BIT array
    for (int i = 0; i <= n; i++) {
        BIT[i] = 0;
    }
 
    for (int i = 0; i < n; i++) {
        // Add elements
        // from left to right
        // in BIT
        update(BIT, arr[i], n);
    }
 
    int ans = query(BIT, n, n);
    return ans;
}
 
// Driver code
int main()
{
 
    int arr[] = { 6, 5, 1, 3, 2, 4, 8, 7 };
    int n = sizeof(arr) / sizeof(int);
    int ans = findLISLength(arr, n);
 
    cout << ans << endl;
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to map numbers using
// coordinate compression
static void coordinateCompression(int arr[],
                                  int n)
{
 
    // Set will store
    // all unique numbers
    Set<Integer> s = new HashSet<>();
    for (int i = 0; i < n; i++)
    {
        s.add(arr[i]);
    }
 
    // Map will store
    // the new elements
    int index = 0;
    HashMap<Integer, Integer> mp =
         new HashMap<Integer, Integer>();
 
    for (int itr : s)
    {
        // For every new number in the set,
        index++;
         
        // Increment the index of the
        // current number and store it
        // in a hashmap. Here index
        // for every element is the
        // new value  with the
        // current element is replaced
        mp.put(itr, index);
    }
    for (int i = 0; i < n; i++)
    {
        // now change the current element
        // to range 1 to N.
        arr[i] = mp.get(arr[i]);
    }
}
 
// Function to calculate length of maximum
// increasing sequence till i'th index
static int query(int BIT[], int index, int n)
{
    int ans = 0;
    while (index > 0)
    {
        ans = Math.max(ans, BIT[index]);
         
        // Go to parent node
        index -= index & (-index);
    }
    return ans;
}
 
// Function for updating BIT array for
// maximum increasing sequence till
// i'th index
static void update(int BIT[],
                   int index, int n)
{
 
    // If 4 is inserted in BIT,
    // check for maximum length
    // subsequence till element 3.
    // Let this subsequence length be x.
    // If x + 1 is greater than
    // the current element in BIT,
    // update the BIT array
    int x = query(BIT, index - 1, n);
    int value = x + 1;
    while (index <= n)
    {
 
        // Store maximum length subsequence length
        // till index. Here index is the
        // coordinate compressed element
        BIT[index] = Math.max(BIT[index], value);
 
        // Go to child node and update that node
        index += index & (-index);
    }
}
 
// Function to calculate maximum
// Longest Increasing Sequence length
static int findLISLength(int arr[], int n)
{
 
    coordinateCompression(arr, n);
    int []BIT = new int[n + 1];
 
    // Initialising BIT array
    for (int i = 0; i <= n; i++)
    {
        BIT[i] = 0;
    }
 
    for (int i = 0; i < n; i++)
    {
        // Add elements from left to right
        // in BIT
        update(BIT, arr[i], n);
    }
 
    int ans = query(BIT, n, n);
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 6, 5, 1, 3, 2, 4, 8, 7 };
    int n = arr.length;
    int ans = findLISLength(arr, n);
 
    System.out.println(ans);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program for the above approach
 
# Function to map
# numbers using coordinate
# compression
def coordinateCompression(arr, n):
 
    # Set will store
    # all unique numbers
    s = dict()
    for i in range(n):
        s[arr[i]] = 1
 
    # Map will store
    # the new elements
    index = 0
    mp = dict()
 
    for itr in sorted(s):
         
        # For every new number in the set,
        index += 1
         
        # Increment the index of the
        # current number and store it
        # in a hashmap. Here index
        # for every element is the
        # new value  with the
        # current element is replaced
        mp[itr] = index
    for i in range(n):
         
        # now change the current element
        # to range 1 to N.
        arr[i] = mp[arr[i]]
 
# Function to calculate
# length of maximum
# increasing sequence till
# i'th index
def query(BIT, index, n):
 
    ans = 0
    while (index > 0):
        ans = max(ans, BIT[index])
         
        # Go to parent node
        index -= index & (-index)
    return ans
 
# Function for updating
# BIT array for maximum
# increasing sequence till
# i'th index
def update(BIT, index, n):
 
    # If 4 is inserted in BIT,
    # check for maximum length
    # subsequence till element 3.
    # Let this subsequence length be x.
    # If x + 1 is greater than
    # the current element in BIT,
    # update the BIT array
    x = query(BIT, index - 1, n)
    value = x + 1
    while (index <= n):
 
        # Store maximum length subsequence length till index
        # Here index is the
        # coordinate compressed element
        BIT[index] = max(BIT[index], value)
 
        # Go to child node and update that node
        index += index & (-index)
 
# Function to calculate
# maximum Longest Increasing
# Sequence length
def findLISLength(arr, n):
 
    coordinateCompression(arr, n)
    BIT = [0]*(n + 1)
 
    for i in range(n):
         
        # Add elements
        # from left to right
        # in BIT
        update(BIT, arr[i], n)
 
    ans = query(BIT, n, n)
    return ans
 
# Driver code
arr=[6, 5, 1, 3, 2, 4, 8, 7]
n = len(arr)
ans = findLISLength(arr, n)
 
print(ans)
 
# This code is contributed mohit kumar 29

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to map numbers using
// coordinate compression
static void coordinateCompression(int []arr,
                                  int n)
{
  // Set will store
  // all unique numbers
  HashSet<int> s = new HashSet<int>();
  for (int i = 0; i < n; i++)
  {
    s.Add(arr[i]);
  }
 
  // Map will store
  // the new elements
  int index = 0;
  Dictionary<int,
             int> mp = new Dictionary<int,
                                      int>();
 
  foreach (int itr in s)
  {
    // For every new number in the set,
    index++;
 
    // Increment the index of the
    // current number and store it
    // in a hashmap. Here index
    // for every element is the
    // new value with the
    // current element is replaced
    mp.Add(itr, index);
  }
   
  for (int i = 0; i < n; i++)
  {
    // now change the current element
    // to range 1 to N.
    arr[i] = mp[arr[i]];
  }
}
 
// Function to calculate
// length of maximum increasing
// sequence till i'th index
static int query(int []BIT,
                 int index, int n)
{
  int ans = 0;
  while (index > 0)
  {
    ans = Math.Max(ans,
                   BIT[index]);
 
    // Go to parent node
    index -= index & (-index);
  }
  return ans;
}
 
// Function for updating BIT array for
// maximum increasing sequence till
// i'th index
static void update(int []BIT,
                   int index, int n)
{
  // If 4 is inserted in BIT,
  // check for maximum length
  // subsequence till element 3.
  // Let this subsequence length be x.
  // If x + 1 is greater than
  // the current element in BIT,
  // update the BIT array
  int x = query(BIT, index - 1, n);
  int value = x + 1;
  while (index <= n)
  {
    // Store maximum length subsequence length
    // till index. Here index is the
    // coordinate compressed element
    BIT[index] = Math.Max(BIT[index], value);
 
    // Go to child node and update that node
    index += index & (-index);
  }
}
 
// Function to calculate maximum
// longest Increasing Sequence length
static int findLISLength(int []arr,
                         int n)
{
  coordinateCompression(arr, n);
  int []BIT = new int[n + 1];
 
  // Initialising BIT array
  for (int i = 0; i <= n; i++)
  {
    BIT[i] = 0;
  }
 
  for (int i = 0; i < n; i++)
  {
    // Add elements from
    // left to right in BIT
    update(BIT, arr[i], n);
  }
 
  int ans = query(BIT, n, n) / 2;
  return ans;
}
 
// Driver code
public static void Main(String[] args)
{
  int []arr = {6, 5, 1, 3,
               2, 4, 8, 7};
  int n = arr.Length;
  int ans = findLISLength(arr, n);
  Console.WriteLine(ans);
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// JavaScript implementation of the approach
 
 
// Function to map numbers using
// coordinate compression
function coordinateCompression(arr, n) {
 
    // Set will store
    // all unique numbers
    let s = new Set();
    for (let i = 0; i < n; i++) {
        s.add(arr[i]);
    }
 
    // Map will store
    // the new elements
    let index = 0;
    let mp = new Map();
 
    for (let itr of s) {
        // For every new number in the set,
        index++;
 
        // Increment the index of the
        // current number and store it
        // in a hashmap. Here index
        // for every element is the
        // new value with the
        // current element is replaced
        mp.set(itr, index);
    }
    for (let i = 0; i < n; i++) {
        // now change the current element
        // to range 1 to N.
        arr[i] = mp.get(arr[i]);
    }
}
 
// Function to calculate length of maximum
// increasing sequence till i'th index
function query(BIT, index, n) {
    let ans = 0;
    while (index > 0) {
        ans = Math.max(ans, BIT[index]);
 
        // Go to parent node
        index -= index & (-index);
    }
    return ans;
}
 
// Function for updating BIT array for
// maximum increasing sequence till
// i'th index
function update(BIT, index, n) {
 
    // If 4 is inserted in BIT,
    // check for maximum length
    // subsequence till element 3.
    // Let this subsequence length be x.
    // If x + 1 is greater than
    // the current element in BIT,
    // update the BIT array
    let x = query(BIT, index - 1, n);
    let value = x + 1;
    while (index <= n) {
 
        // Store maximum length subsequence length
        // till index. Here index is the
        // coordinate compressed element
        BIT[index] = Math.max(BIT[index], value);
 
        // Go to child node and update that node
        index += index & (-index);
    }
}
 
// Function to calculate maximum
// Longest Increasing Sequence length
function findLISLength(arr, n) {
 
    coordinateCompression(arr, n);
    let BIT = new Array(n + 1);
 
    // Initialising BIT array
    for (let i = 0; i <= n; i++) {
        BIT[i] = 0;
    }
 
    for (let i = 0; i < n; i++) {
        // Add elements from left to right
        // in BIT
        update(BIT, arr[i], n);
    }
 
    let ans = query(BIT, n, n) / 2;
    return ans;
}
 
// Driver code
 
 
let arr = [6, 5, 1, 3, 2, 4, 8, 7];
let n = arr.length;
let ans = findLISLength(arr, n);
 
document.write(ans);
 
 
// This code is contributed by _saurabh_jaiswal
 
</script>
Producción: 

4

 

Complejidad de tiempo: O(N*log(N))

Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por Utkarsh Raj 4 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *