Find longest bitonic sequence such that increasing and decreasing parts are from two different arrays | CPP to find largest bitonic sequence such that ; utility Binary search ; function to find LIS in reverse form ; int len = 1 ; it will always point to empty location ; new smallest value ; arr [ i ] wants to extend largest subsequence ; arr [ i ] wants to be a potential candidate of future subsequence It will replace ceil value in tailIndices ; put LIS into vector ; function for finding longest bitonic seq ; find LIS of array 1 in reverse form ; reverse res to get LIS of first array ; reverse array2 and find its LIS ; print result ; driver preogram
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > res ; 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 ; } void LIS ( int arr [ ] , int n ) { for ( int i = 1 ; i < n ; i ++ ) { if ( arr [ i ] < arr [ tailIndices [ 0 ] ] ) tailIndices [ 0 ] = i ; else if ( arr [ i ] > arr [ tailIndices [ len - 1 ] ] ) { prevIndices [ i ] = tailIndices [ len - 1 ] ; tailIndices [ len ++ ] = i ; } else { int pos = GetCeilIndex ( arr , tailIndices , -1 , len - 1 , arr [ i ] ) ; prevIndices [ i ] = tailIndices [ pos - 1 ] ; tailIndices [ pos ] = i ; } } for ( int i = tailIndices [ len - 1 ] ; i >= 0 ; i = prevIndices [ i ] ) res . push_back ( arr [ i ] ) ; } void longestBitonic ( int arr1 [ ] , int n1 , int arr2 [ ] , int n2 ) { LIS ( arr1 , n1 ) ; reverse ( res . begin ( ) , res . end ( ) ) ; reverse ( arr2 , arr2 + n2 ) ; LIS ( arr2 , n2 ) ; for ( int i = 0 ; i < res . size ( ) ; i ++ ) cout << res [ i ] << " ▁ " ; } 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 ; }