Самая длинная возрастающая подпоследовательность с использованием BIT

Опубликовано: 5 Января, 2022

Учитывая массив arr , задача состоит в том, чтобы найти длину самой длинной возрастающей последовательности с использованием двоичного индексированного дерева (BIT)
Примеры:

 Ввод: arr = {6, 5, 1, 3, 2, 4, 8, 7}
Выход: 4
Пояснение:
Возможные подпоследовательности: 
{1 2 4 7}, {1 2 4 8}, 
{1 3 4 8}, {1 3 4 7}  

Теперь вставьте элементы по очереди слева направо:

Вставлено 6: максимальная длина до 5 = 0, а для 6 - 1
Вставлено 5: максимальная длина до 4 = 0, а для 5 - 1
Вставлен 1: максимальная длина до 0 = 2, для 1 - 1
Вставлено 3: максимальная длина до 2 = 1, а для 3 - 2
2 вставлено: максимальная длина до 1 = 1, ответ для 2 равен 2
Вставлено 4: максимальная длина до 3 = 2, а для 4 - 3
Вставлено 8: максимальная длина до 7 = 3, а для 8 - 4
Вставлено 7: максимальная длина до 6 = 3, а для 7 - 4

Ввод: arr = {1, 2, 3, 4, 1, 5}
Выход: 5



Предпосылка для этой публикации: двоичное индексированное дерево

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

  • Сначала используйте сжатие координат (замените все значения массива на числа от 1 до N). Это уменьшит максимальное число в массиве и поможет нам решить указанную выше проблему за время NlogN. Кроме того, это поможет нам уменьшить объем памяти.
  • Создайте новый массив BIT длины N + 1.
  • Теперь пройдитесь по массиву слева направо и добавьте текущий элемент в BIT.
  • Когда i-й элемент (A [i]) вставлен в BIT, проверьте длину самой длинной подпоследовательности, которая может быть сформирована до A [i] - 1. Пусть это значение будет x. Если x + 1 больше, чем текущий элемент в BIT, обновите BIT.

Ниже представлена реализация описанного выше подхода:

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 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
// Sequene length
int findLISLength( int arr[], int n)
{
coordinateCompression(arr, n);
int BIT[n + 1];
// Intialising 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 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 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 query( int 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 update( void 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 Sequene length
static int findLISLength( int arr[], int n)
{
coordinateCompression(arr, n);
int []BIT = new int [n + 1 ];
// Intialising 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 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
# Sequene 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 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 query( int 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 Sequene length
static int findLISLength( int []arr,
int n)
{
coordinateCompression(arr, n);
int []BIT = new int [n + 1];
// Intialising BIT array
for ( int i = 0; i <= n; i++)
{
BIT[i] = 0;
}
for ( int i = 0; i < n; i++)
{