Самая длинная возрастающая подпоследовательность с использованием 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++) { РЕКОМЕНДУЕМЫЕ СТАТЬИ |