Find longest bitonic sequence such that increasing and decreasing parts are from two different arrays | JavaScript to find largest bitonic sequence such that ; utility Binary search ; function to find LIS in reverse form ; Add boundary case , when array n is zero Depend on smart pointers ; 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 Code
let res = [ ] ; 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 LIS ( arr , n ) { let tailIndices = new Array ( n ) ; let prevIndices = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { tailIndices [ i ] = 0 ; prevIndices [ i ] = - 1 ; } let len = 1 ; for ( let 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 { let pos = GetCeilIndex ( arr , tailIndices , - 1 , len - 1 , arr [ i ] ) ; prevIndices [ i ] = tailIndices [ pos - 1 ] ; tailIndices [ pos ] = i ; } } for ( let i = tailIndices [ len - 1 ] ; i >= 0 ; i = prevIndices [ i ] ) res . push ( arr [ i ] ) ; } function longestBitonic ( arr1 , n1 , arr2 , n2 ) { LIS ( arr1 , n1 ) ; res . reverse ( ) ; arr2 . reverse ( ) ; LIS ( arr2 , n2 ) ; for ( let i = 0 ; i < res . length ; i ++ ) document . write ( res [ i ] + " " ) ; } 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 ) ;