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