We are given two arrays, we need to find the longest possible bitonic sequence such that the increasing part must be from the first array and should be a subsequence of the first array. Similarly, the decreasing part of must be from the second array and should be a subsequence of it.
Examples:
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
The idea is to use the largest increasing sequence from array1 and the largest decreasing sequence from array2 and then combine both to get our result.
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> |
1 2 3 8 6 4
Time Complexity : O(n Log n)
Auxiliary Space: O(n)
Please note that O(n Log n) implementation of LIS is used
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!