Nos dan dos arrays, necesitamos encontrar la secuencia bitónica más larga posible de modo que la parte creciente debe ser de la primera array y debe ser una subsecuencia de la primera array. De manera similar, la parte decreciente de debe ser del segundo arreglo y debe ser una subsecuencia del mismo.
Ejemplos:
Input : arr1[] = {1, 5, 2, 4, 3, 5}, arr2[] = {8, 6, 4, 7, 3, 2} Output : 1, 2, 4, 5, 8, 6, 4, 3, 2 Input : arr1[] = {2, 0, 1, 3, 4}, arr2[] = {5, 3, 2, 1} Output : 0, 1, 2, 3, 4, 5, 3, 2, 1
La idea es usar la secuencia creciente más grande de array1 y la secuencia decreciente más grande de array2 y luego combinar ambas para obtener nuestro resultado.
C++
// CPP to find largest bitonic sequence such that #include <bits/stdc++.h> using namespace std; vector<int> res; // utility Binary search int GetCeilIndex(int arr[], vector<int>& T, int l, int r, int key) { while (r - l > 1) { int m = l + (r - l) / 2; if (arr[T[m]] >= key) r = m; else l = m; } return r; } // function to find LIS in reverse form void LIS(int arr[], int n) { // Add boundary case, when array n is zero // Depend on smart pointers vector<int> tailIndices(n, 0); // Initialized with 0 vector<int> prevIndices(n, -1); // initialized with -1 int len = 1; // it will always point to empty location for (int i = 1; i < n; i++) { // new smallest value if (arr[i] < arr[tailIndices[0]]) tailIndices[0] = i; // arr[i] wants to extend largest subsequence else if (arr[i] > arr[tailIndices[len - 1]]) { prevIndices[i] = tailIndices[len - 1]; tailIndices[len++] = i; } // arr[i] wants to be a potential candidate of // future subsequence // It will replace ceil value in tailIndices else { int pos = GetCeilIndex(arr, tailIndices, -1, len - 1, arr[i]); prevIndices[i] = tailIndices[pos - 1]; tailIndices[pos] = i; } } // put LIS into vector for (int i = tailIndices[len - 1]; i >= 0; i = prevIndices[i]) res.push_back(arr[i]); } // function for finding longest bitonic seq void longestBitonic(int arr1[], int n1, int arr2[], int n2) { // find LIS of array 1 in reverse form LIS(arr1, n1); // reverse res to get LIS of first array reverse(res.begin(), res.end()); // reverse array2 and find its LIS reverse(arr2, arr2 + n2); LIS(arr2, n2); // print result for (int i = 0; i < res.size(); i++) cout << res[i] << " "; } // driver preogram int main() { int arr1[] = { 1, 2, 4, 3, 2 }; int arr2[] = { 8, 6, 4, 7, 8, 9 }; int n1 = sizeof(arr1) / sizeof(arr1[0]); int n2 = sizeof(arr2) / sizeof(arr2[0]); longestBitonic(arr1, n1, arr2, n2); return 0; }
Java
// Java to find largest bitonic sequence such that import java.util.*; class GFG { static Vector<Integer> res = new Vector<>(); // utility Binary search static Integer GetCeilIndex(Integer[] arr, Integer[] T, Integer l, Integer r, Integer key) { while (r - l > 1) { Integer m = l + (r - l) / 2; if (arr[T[m]] >= key) r = m; else l = m; } return r; } // function to find LIS in reverse form static void LIS(Integer[] arr, Integer n) { // Add boundary case, when array n is zero // Depend on smart pointers Integer[] tailIndices = new Integer[n]; Integer[] prevIndices = new Integer[n]; Arrays.fill(tailIndices, 0); // Initialized with 0 Arrays.fill(prevIndices, -1); // initialized with -1 Integer len = 1; // it will always point to empty location for (Integer i = 1; i < n; i++) { // new smallest value if (arr[i] < arr[tailIndices[0]]) tailIndices[0] = i; // arr[i] wants to extend largest subsequence else if (arr[i] > arr[tailIndices[len - 1]]) { prevIndices[i] = tailIndices[len - 1]; tailIndices[len++] = i; } // arr[i] wants to be a potential candidate of // future subsequence // It will replace ceil value in tailIndices else { Integer pos = GetCeilIndex(arr, tailIndices, -1, len - 1, arr[i]); prevIndices[i] = tailIndices[pos - 1]; tailIndices[pos] = i; } } // put LIS into vector for (Integer i = tailIndices[len - 1]; i >= 0; i = prevIndices[i]) res.add(arr[i]); } // function for finding longest bitonic seq static void longestBitonic(Integer[] arr1, Integer n1, Integer[] arr2, Integer n2) { // find LIS of array 1 in reverse form LIS(arr1, n1); // reverse res to get LIS of first array Collections.reverse(res); // reverse array2 and find its LIS Collections.reverse(Arrays.asList(arr2)); LIS(arr2, n2); // print result for (Integer i = 0; i < res.size(); i++) System.out.print(res.elementAt(i) + " "); } // Driver Code public static void main(String[] args) { Integer[] arr1 = { 1, 2, 4, 3, 2 }; Integer[] arr2 = { 8, 6, 4, 7, 8, 9 }; Integer n1 = arr1.length; Integer n2 = arr2.length; longestBitonic(arr1, n1, arr2, n2); } } // This code is contributed by // sanjeev2552
Python3
# Python3 to find largest bitonic sequence such that res = [] # utility Binary search def GetCeilIndex(arr,T, l,r, key): while (r - l > 1): m = l + (r - l) // 2; if (arr[T[m]] >= key): r = m else: l = m return r # function to find LIS in reverse form def LIS(arr, n): # Add boundary case, when array n is zero # Depend on smart pointers tailIndices = [0]*(n) #Initialized with 0 prevIndices = [-1]*(n) #initialized with -1 leN = 1 # it will always point to empty location for i in range(1, n): # new smallest value if (arr[i] < arr[tailIndices[0]]): tailIndices[0] = i # arr[i] wants to extend largest subsequence else if (arr[i] > arr[tailIndices[leN - 1]]): prevIndices[i] = tailIndices[leN - 1] tailIndices[leN] = i leN += 1 # arr[i] wants to be a potential candidate of # future subsequence # It will replace ceil value in tailIndices else: pos = GetCeilIndex(arr, tailIndices, -1, leN - 1, arr[i]) prevIndices[i] = tailIndices[pos - 1] tailIndices[pos] = i # put LIS into vector i = tailIndices[leN - 1] while(i >= 0): # print(i) res.append(arr[i]) i = prevIndices[i] # function for finding longest bitonic seq def longestBitonic(arr1, n1, arr2, n2): global res # find LIS of array 1 in reverse form LIS(arr1, n1) # reverse res to get LIS of first array res = res[::-1] # reverse array2 and find its LIS arr2 = arr2[::-1] LIS(arr2, n2) # print result for i in res: print(i,end=" ") # Driver program arr1 = [1, 2, 4, 3, 2] arr2 = [8, 6, 4, 7, 8, 9] n1 = len(arr1) n2 = len(arr2) longestBitonic(arr1, n1, arr2, n2); # This code is contributed by mohit kumar 29
C#
// C# to find largest bitonic // sequence using System; using System.Collections.Generic; class GFG{ static List<int> res = new List<int>(); // Reverse array static int[] reverse(int []a) { int i, n = a.Length, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a; } // Utility Binary search static int GetCeilIndex(int[] arr, int[] T, int l, int r, int key) { while (r - l > 1) { int m = l + (r - l) / 2; if (arr[T[m]] >= key) r = m; else l = m; } return r; } // Function to find LIS in reverse form static void LIS(int[] arr, int n) { // Add boundary case, // when array n is zero // Depend on smart pointers int[] tailIndices = new int[n]; int[] prevIndices = new int[n]; for(int i = 0; i < n; i++) { tailIndices[i] = 0; prevIndices[i] = -1; } int len = 1; // It will always point // to empty location for (int i = 1; i < n; i++) { // New smallest value if (arr[i] < arr[tailIndices[0]]) tailIndices[0] = i; // arr[i] wants to extend // largest subsequence else if (arr[i] > arr[tailIndices[len - 1]]) { prevIndices[i] = tailIndices[len - 1]; tailIndices[len++] = i; } // arr[i] wants to be // a potential candidate of // future subsequence // It will replace ceil // value in tailIndices else { int pos = GetCeilIndex(arr, tailIndices, -1, len - 1, arr[i]); prevIndices[i] = tailIndices[pos - 1]; tailIndices[pos] = i; } } // Put LIS into vector for (int i = tailIndices[len - 1]; i >= 0; i = prevIndices[i]) res.Add(arr[i]); } // Function for finding longest bitonic seq static void longestBitonic(int[] arr1, int n1, int[] arr2, int n2) { // Find LIS of array 1 // in reverse form LIS(arr1, n1); // Reverse res to get // LIS of first array res.Reverse(); // Reverse array2 and // find its LIS arr2 = reverse(arr2); LIS(arr2, n2); // Print result for (int i = 0; i < res.Count; i++) Console.Write(res[i] + " "); } // Driver Code public static void Main(String[] args) { int[] arr1 = {1, 2, 4, 3, 2}; int[] arr2 = {8, 6, 4, 7, 8, 9}; int n1 = arr1.Length; int n2 = arr2.Length; longestBitonic(arr1, n1, arr2, n2); } } // This code is contributed by gauravrajput1
Javascript
<script> // JavaScript to find largest // bitonic sequence such that let res = []; // utility Binary search function GetCeilIndex(arr,T,l,r,key) { while (r - l > 1) { let m = l + Math.floor((r - l) / 2); if (arr[T[m]] >= key) r = m; else l = m; } return r; } // function to find LIS in reverse form function LIS(arr,n) { // Add boundary case, when array n is zero // Depend on smart pointers let tailIndices = new Array(n); let prevIndices = new Array(n); for(let i=0;i<n;i++) { tailIndices[i]=0; prevIndices[i]=-1; } // it will always point to empty location let len = 1; for (let i = 1; i < n; i++) { // new smallest value if (arr[i] < arr[tailIndices[0]]) tailIndices[0] = i; // arr[i] wants to extend largest subsequence else if (arr[i] > arr[tailIndices[len - 1]]) { prevIndices[i] = tailIndices[len - 1]; tailIndices[len++] = i; } // arr[i] wants to be a potential candidate of // future subsequence // It will replace ceil value in tailIndices else { let pos = GetCeilIndex(arr, tailIndices, -1, len - 1, arr[i]); prevIndices[i] = tailIndices[pos - 1]; tailIndices[pos] = i; } } // put LIS into vector for (let i = tailIndices[len - 1]; i >= 0; i = prevIndices[i]) res.push(arr[i]); } // function for finding longest bitonic seq function longestBitonic(arr1,n1,arr2,n2) { // find LIS of array 1 in reverse form LIS(arr1, n1); // reverse res to get LIS of first array res.reverse(); // reverse array2 and find its LIS arr2.reverse(); LIS(arr2, n2); // print result for (let i = 0; i < res.length; i++) document.write(res[i] + " "); } // Driver Code let arr1=[1, 2, 4, 3, 2]; let arr2=[8, 6, 4, 7, 8, 9]; let n1 = arr1.length; let n2 = arr2.length; longestBitonic(arr1, n1, arr2, n2); // This code is contributed by patel2127 </script>
Producción:
1 2 3 8 6 4
Complejidad de tiempo: O(n Log n)
Tenga en cuenta que se utiliza la implementación O(n Log n) de LIS
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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