Dada una array arr[0 … n-1] que contiene n enteros positivos, una subsecuencia de arr[] se llama bitónica si primero es creciente y luego decreciente. Escriba una función que tome una array como argumento y devuelva la longitud de la subsecuencia bitónica más larga.
Una secuencia ordenada en orden creciente se considera bitónica con la parte decreciente vacía. De manera similar, la secuencia de orden decreciente se considera bitónica con la parte creciente como vacía.
Complejidad de tiempo esperada: O (n log n)
Ejemplos:
Input arr[] = {1, 11, 2, 10, 4, 5, 2, 1}; Output: 6 Explanation : A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1 Input arr[] = {12, 11, 40, 5, 3, 1} Output: 5 Explanation : A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1) Input arr[] = {80, 60, 30, 40, 20, 10} Output: 5 Explanation : A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)
Hemos discutido la solución O(n 2 ) en Programación Dinámica | Conjunto 15 (Subsecuencia bitónica más larga)
La idea es seguir el tamaño de la subsecuencia creciente más larga (n log n) para ver la forma en que se calcula la longitud de la subsecuencia creciente más larga (LIS).
Algoritmo:
Step 1: Define 4 Auxiliary arrays of size n: increasing[n] to calculate LIS of the array tail1[n] to store the values for LIS for increasing[n] decreasing[n] to calculate LIS of the array tail2[n] to store the values for LIS for decreasing[n] Step 2: Find LIS for increasing array Step 3: Reverse array and store it in decreasing Step 4: Find LIS for decreasing array Step 5: Longest Bitonicc SubSequence length now will be max of tail1[i] + tail2[i] + 1
Implementación:
C++
// C++ program to find length of longest // Bitonic subsequence in O (n Log n( time, #include <bits/stdc++.h> using namespace std; // Binary Search int ceilIndex(int arr[], int l, int r, int x) { if (l > r) return -1; int mid = l + (r - l) / 2; if (arr[mid] == x) return mid; if (x < arr[mid]) return ceilIndex(arr, l, mid - 1, x); return ceilIndex(arr, mid + 1, r, x); } // function to reverse an array void revereseArr(int arr[], int n) { int i = 0; int j = n - 1; while (i < j) swap(arr[i++], arr[j--]); } // Returns length of longest Bitonic // subsequence in O(n Log n) time. int getLBSLengthLogn(int arr[], int n) { // Base Case: if (n == 0) return 0; // Aux array storing the input array // in same order to calculate LIS: int increasing[n]; int tail1[n]; // To store lengths of IS // Aux array storing the input array // in reverse order to calculate LIS: // This will calculate Longest Decreasing // Subsequence which is required for // Longest Bitonic Subsequence int decreasing[n]; int tail2[n]; // To store lengths of DS // initializing first index same as // original array: increasing[0] = arr[0]; // index in initialized as 1 from where // the remaining computations will be done int in = 1; // tail1 stores Longest Increasing subsequence // length values till index in tail1[0] = 0; // remaining computations to get the // LIS length for increasing for (int i = 1; i < n; i++) { if (arr[i] < increasing[0]) { increasing[0] = arr[i]; tail1[i] = 0; } else if (arr[i] > increasing[in - 1]) { increasing[in++] = arr[i]; tail1[i] = in - 1; } else { increasing[ceilIndex(increasing, -1, in - 1, arr[i])] = arr[i]; tail1[i] = ceilIndex(increasing, -1, in - 1, arr[i]); } } // reiitializing the index to 1 in = 1; // reversing the array to get the Longest // Decreasing Subsequence Length: revereseArr(arr, n); decreasing[0] = arr[0]; tail2[0] = 0; for (int i = 1; i < n; i++) { if (arr[i] < decreasing[0]) { decreasing[0] = arr[i]; tail2[i] = 0; } else if (arr[i] > decreasing[in - 1]) { decreasing[in++] = arr[i]; tail2[i] = in - 1; } else { decreasing[ceilIndex(decreasing, -1, in - 1, arr[i])] = arr[i]; tail2[i] = ceilIndex(decreasing, -1, in - 1, arr[i]); } } revereseArr(arr, n); revereseArr(tail2, n); // Longest Bitonic Subsequence length is // maximum of tail1[i] + tail2[i] + 1: int ans = 0; for (int i = 0; i < n; i++) if (ans < (tail1[i] + tail2[i] + 1)) ans = (tail1[i] + tail2[i] + 1); return ans; } // Driver code int main() { int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int n = sizeof(arr) / sizeof(arr[0]); cout << getLBSLengthLogn(arr, n) << endl; return 0; }
Java
// Java program to find length of longest // Bitonic subsequence in O (n Log n) time, import java.util.Arrays; public class GFG { // function to reverse an array static void revereseArr(int arr[]) { int i = 0; int j = arr.length - 1; while (i < j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++;j--; } } // Returns length of longest Bitonic // subsequence in O(n Log n) time. static int getLBSLengthLogn(int arr[]) { int n = arr.length; // Base Case: if(n==0) return 0; /*Aux array storing the input array in same order to calculate LIS:*/ int increasing[] = new int[n]; //to store lengths of IS int tail1[] = new int[n]; /*Aux array storing the input array in reverse order to calculate LIS: This will calculate Longest Decreasing Subsequence which is required for Longest Bitonic Subsequence*/ int decreasing[] = new int[n]; // To store lengths of DS int tail2[] = new int[n]; // initializing first index same as // original array: increasing[0] = arr[0]; // index in initialized as 1 from where // the remaining computations will be done int in = 1; // tail1 stores Longest Increasing // subsequence length values till index in tail1[0] = 0; // remaining computations to get the // LIS length for increasing for(int i = 1; i < n; i++) { if(arr[i] < increasing[0]) { increasing[0] = arr[i]; tail1[i] = 0; } else if(arr[i] > increasing[in - 1]) { increasing[in++] = arr[i]; tail1[i] = in - 1; } else { int getIndex1 = Arrays.binarySearch(increasing, 0, in, arr[i]); if(getIndex1 <= -1) continue; increasing[getIndex1] = arr[i]; tail1[i] = getIndex1; } } // reinitializing the index to 1 in = 1; // reversing the array to get the Longest // Decreasing Subsequence Length: revereseArr(arr); decreasing[0] = arr[0]; tail2[0] = 0; for(int i = 0; i < n; i++) { if(arr[i] < decreasing[0]) { decreasing[0] = arr[i]; tail2[i] = 0; } else if(arr[i] > decreasing[in - 1]) { decreasing[in++] = arr[i]; tail2[i] = in - 1; } else { int getIndex2 = Arrays.binarySearch(decreasing, 0, in , arr[i]); if(getIndex2 <= -1) continue; decreasing[getIndex2] = arr[i]; tail2[i] = getIndex2; } } revereseArr(arr); revereseArr(tail2); // Longest Bitonic Subsequence length is // maximum of tail1[i] + tail2[i] + 1: int ans = 0; for (int i = 0; i < n; i++) { if (ans < (tail1[i] + tail2[i] + 1)) ans = (tail1[i] + tail2[i] + 1); } return ans; } // Driver code to test above methods public static void main(String[] args) { int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; System.out.println(getLBSLengthLogn(arr)); } } // This code is contributed by Sumit Ghosh
Python3
# Python3 program to find length of longest # Bitonic subsequence in O (n Log n) time # Binary Search def ceilIndex(arr, l, r, x): if (l > r): return -1 mid = l + (r - l) // 2 if (arr[mid] == x): return mid if (x < arr[mid]): return ceilIndex(arr, l, mid - 1, x) return ceilIndex(arr, mid + 1, r, x) # Function to reverse an array def revereseArr(arr, n): i = 0 j = n - 1 while (i < j): t = arr[i] arr[i] = arr[j] arr[j] = t i += 1 j -= 1 # Returns length of longest Bitonic # subsequence in O(n Log n) time. def getLBSLengthLogn(arr, n): # Base Case: if (n == 0): return 0 # Aux array storing the input array # in same order to calculate LIS: increasing = [0 for i in range(n)] tail1 = [0 for i in range(n)] # To store lengths of LIS # Aux array storing the input array # in reverse order to calculate LIS: # This will calculate Longest Decreasing # Subsequence which is required for # Longest Bitonic Subsequence decreasing = [0 for i in range(n)] tail2 = [0 for i in range(n)] # To store lengths of DS # initializing first index same as # original array: increasing [0] = arr [0] # index in initialized as 1 from where # the remaining computations will be done ind = 1 # tail1 stores Longest Increasing subsequence # length values till index in tail1[0] = 0 # remaining computations to get the # LIS length for increasing for i in range(1, n): if (arr[i] < increasing[0]): increasing[0] = arr[i] tail1[i] = 0 else if (arr[i] > increasing[ind - 1]): increasing[ind] = arr[i] ind += 1 tail1[i] = ind - 1 else: increasing[ceilIndex(increasing, -1, ind - 1, arr[i])] = arr[i] tail1[i] = ceilIndex(increasing, -1, ind- 1, arr[i]) # reinitializing the index to 1 ind = 1 # reversing the array to get the Longest # Decreasing Subsequence Length: revereseArr(arr, n) decreasing[0] = arr[0] tail2[0] = 0 for i in range(1, n): if (arr[i] < decreasing[0]): decreasing[0] = arr[i] tail2[i] = 0 else if (arr[i] > decreasing[ind - 1]): decreasing[ind] = arr[i] ind += 1 tail2[i] = ind - 1 else: decreasing[ceilIndex(decreasing, -1, ind - 1, arr[i])] = arr[i] tail2[i] = ceilIndex(decreasing, -1, ind - 1, arr[i]) revereseArr(arr, n) revereseArr(tail2, n) # Longest Bitonic Subsequence length is # maximum of tail1[i] + tail2[i] + 1: ans = 0 for i in range(n): if (ans < (tail1[i] + tail2[i] + 1)): ans = (tail1[i] + tail2[i] + 1) return ans # Driver code arr = [ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] n = len(arr) print (getLBSLengthLogn(arr, n)) # This code is contributed by Sachin Bisht
C#
// C# program to find length of longest // Bitonic subsequence in O (n Log n) time, using System; public class GFG { // function to reverse an array static void revereseArr(int []arr) { int i = 0; int j = arr.Length - 1; while (i < j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } // Returns length of longest Bitonic // subsequence in O(n Log n) time. static int getLBSLengthLogn(int []arr) { int n = arr.Length; // Base Case: if(n == 0) return 0; /*Aux array storing the input array in same order to calculate LIS:*/ int []increasing = new int[n]; //to store lengths of IS int []tail1 = new int[n]; /*Aux array storing the input array in reverse order to calculate LIS: This will calculate Longest Decreasing Subsequence which is required for Longest Bitonic Subsequence*/ int []decreasing = new int[n]; // To store lengths of DS int []tail2 = new int[n]; // initializing first index same as // original array: increasing[0] = arr[0]; // index in initialized as 1 from where // the remaining computations will be done int inn = 1; // tail1 stores Longest Increasing // subsequence length values till index in tail1[0] = 0; // remaining computations to get the // LIS length for increasing for(int i = 1; i < n; i++) { if(arr[i] < increasing[0]) { increasing[0] = arr[i]; tail1[i] = 0; } else if(arr[i] > increasing[inn - 1]) { increasing[inn++] = arr[i]; tail1[i] = inn - 1; } else { int getIndex1 = Array.BinarySearch(increasing, 0, inn, arr[i]); if(getIndex1 <= -1) continue; increasing[getIndex1] = arr[i]; tail1[i] = getIndex1; } } // reinitializing the index to 1 inn = 1; // reversing the array to get the Longest // Decreasing Subsequence Length: revereseArr(arr); decreasing[0] = arr[0]; tail2[0] = 0; for(int i = 0; i < n; i++) { if(arr[i] < decreasing[0]) { decreasing[0] = arr[i]; tail2[i] = 0; } else if(arr[i] > decreasing[inn - 1]) { decreasing[inn++] = arr[i]; tail2[i] = inn - 1; } else { int getIndex2 = Array.BinarySearch(decreasing, 0, inn , arr[i]); if(getIndex2 <= -1) continue; decreasing[getIndex2] = arr[i]; tail2[i] = getIndex2; } } revereseArr(arr); revereseArr(tail2); // Longest Bitonic Subsequence length is // maximum of tail1[i] + tail2[i] + 1: int ans = 0; for (int i = 0; i < n; i++) { if (ans < (tail1[i] + tail2[i] + 1)) ans = (tail1[i] + tail2[i] + 1); } return ans; } // Driver code to test above methods public static void Main() { int []arr = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; Console.Write(getLBSLengthLogn(arr)); } } // This code is contributed by nitin mittal.
PHP
<?php // PHP program to find length of longest // Bitonic subsequence in O (n Log n( time, // Binary Search function ceilIndex(&$arr, $l, $r, $x) { if ($l > $r) return -1; $mid = intval($l + ($r - $l) / 2); if ($arr[$mid] == $x) return $mid; if ($x < $arr[$mid]) return ceilIndex($arr, $l, $mid - 1, $x); return ceilIndex($arr, $mid + 1, $r, $x); } // function to reverse an array function revereseArr(&$arr, $n) { $i = 0; $j = $n - 1; while ($i < $j) { $temp = $arr[$i]; $arr[$i] = $arr[$j]; $arr[$j] = $temp; $i++; $j--; } } // Returns length of longest Bitonic // subsequence in O(n Log n) time. function getLBSLengthLogn(&$arr, $n) { // Base Case: if ($n == 0) return 0; // Aux array storing the input array // in same order to calculate LIS: $increasing = array_fill(0, $n, NULL); $tail1 = array_fill(0, $n, NULL); // To store lengths of IS // Aux array storing the input array // in reverse order to calculate LIS: // This will calculate Longest Decreasing // Subsequence which is required for // Longest Bitonic Subsequence $decreasing = array_fill(0, $n, NULL); $tail2 = array_fill(0, $n, NULL); // To store lengths of DS // initializing first index same as // original array: $increasing[0] = $arr[0]; // index in initialized as 1 from where // the remaining computations will be done $in = 1; // tail1 stores Longest Increasing // subsequence length values till index in $tail1[0] = 0; // remaining computations to get the // LIS length for increasing for ($i = 1; $i < $n; $i++) { if ($arr[$i] < $increasing[0]) { $increasing[0] = $arr[$i]; $tail1[$i] = 0; } else if ($arr[$i] > $increasing[$in - 1]) { $increasing[$in++] = $arr[$i]; $tail1[$i] = $in - 1; } else { $increasing[ceilIndex($increasing, -1, $in - 1, $arr[$i])] = $arr[$i]; $tail1[$i] = ceilIndex($increasing, -1, $in - 1, $arr[$i]); } } // reiitializing the index to 1 $in = 1; // reversing the array to get the Longest // Decreasing Subsequence Length: revereseArr($arr, $n); $decreasing[0] = $arr[0]; $tail2[0] = 0; for ($i = 1; $i < $n; $i++) { if ($arr[$i] < $decreasing[0]) { $decreasing[0] = $arr[$i]; $tail2[$i] = 0; } else if ($arr[$i] > $decreasing[$in - 1]) { $decreasing[$in++] = $arr[$i]; $tail2[$i] = $in - 1; } else { $decreasing[ceilIndex($decreasing, -1, $in - 1, $arr[$i])] = $arr[$i]; $tail2[$i] = ceilIndex($decreasing, -1, $in - 1, $arr[$i]); } } revereseArr($arr, $n); revereseArr($tail2, $n); // Longest Bitonic Subsequence length is // maximum of tail1[i] + tail2[i] + 1: $ans = 0; for ($i = 0; $i < $n; $i++) if ($ans < ($tail1[$i] + $tail2[$i] + 1)) $ans = ($tail1[$i] + $tail2[$i] + 1); return $ans; } // Driver code $arr = array(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15); $n = sizeof($arr); echo getLBSLengthLogn($arr, $n) . "\n"; // This code is contributed by ita_c ?>
Javascript
<script> // Javascript program to find length of longest // Bitonic subsequence in O (n Log n) time, function binarySearch(arr, x, start, end) { // Base Condition if (start > end) return false; // FInd the middle Index let mid=Math.floor((start + end)/2); // Compare mid with given key x if (arr[mid]===x) return true; // If element at mid is greater than x, // search In the left half of mid if(arr[mid] > x) return binarySearch(arr, x, start, mid-1); else // If element at mid is smaller than x, // search In the right half of mid return binarySearch(arr, x, mid+1, end); } // function to reverse an array function revereseArr(arr) { let i = 0; let j = arr.length - 1; while (i < j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++;j--; } } // Returns length of longest Bitonic // subsequence in O(n Log n) time. function getLBSLengthLogn(arr) { let n = arr.length; // Base Case: if(n==0) return 0; /*Aux array storIng the Input array In same order to calculate LIS:*/ let IncreasIng = new Array(n); //to store lengths of IS let tail1 = new Array(n); /*Aux array storIng the Input array In reverse order to calculate LIS: This will calculate Longest DecreasIng Subsequence which is required for Longest Bitonic Subsequence*/ let decreasIng = new Array(n); // To store lengths of DS let tail2 = new Array(n); // InitializIng first Index same as // origInal array: IncreasIng[0] = arr[0]; // Index In Initialized as 1 from where // the remaInIng computations will be done let In = 1; // tail1 stores Longest IncreasIng // subsequence length values till Index In tail1[0] = 0; // remaInIng computations to get the // LIS length for IncreasIng for(let i = 1; i < n; i++) { if(arr[i] < IncreasIng[0]) { IncreasIng[0] = arr[i]; tail1[i] = 0; } else if(arr[i] > IncreasIng[In - 1]) { IncreasIng[In++] = arr[i]; tail1[i] = In - 1; } else { let getIndex1 = binarySearch(IncreasIng, 0, In, arr[i]); if(getIndex1 <= -1) contInue; IncreasIng[getIndex1] = arr[i]; tail1[i] = getIndex1; } } // reInitializIng the Index to 1 In = 1; // reversIng the array to get the Longest // DecreasIng Subsequence Length: revereseArr(arr); decreasIng[0] = arr[0]; tail2[0] = 0; for(let i = 0; i < n; i++) { if(arr[i] < decreasIng[0]) { decreasIng[0] = arr[i]; tail2[i] = 0; } else if(arr[i] > decreasIng[In - 1]) { decreasIng[In++] = arr[i]; tail2[i] = In - 1; } else { let getIndex2 = binarySearch(decreasIng, 0, In , arr[i]); if(getIndex2 <= -1) contInue; decreasIng[getIndex2] = arr[i]; tail2[i] = getIndex2; } } revereseArr(arr); revereseArr(tail2); // Longest Bitonic Subsequence length is // maximum of tail1[i] + tail2[i] + 1: let ans = 0; for (let i = 0; i < n; i++) { if (ans < (tail1[i] + tail2[i] + 1)) ans = (tail1[i] + tail2[i] + 1); } return ans; } // Driver code to test above methods let arr=[ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]; document.write(getLBSLengthLogn(arr)); // This code is contributed by avanitrachhadiya2155 </script>
7
Complejidad de Tiempo: O(nLogn)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA