Find longest bitonic sequence such that increasing and decreasing parts are from two different arrays | Java 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 ; Integer 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 Code
import java . util . * ; class GFG { static Vector < Integer > res = new Vector < > ( ) ; 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 ; } static void LIS ( Integer [ ] arr , Integer n ) { Integer [ ] tailIndices = new Integer [ n ] ; Integer [ ] prevIndices = new Integer [ n ] ; for ( Integer 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 { Integer pos = GetCeilIndex ( arr , tailIndices , - 1 , len - 1 , arr [ i ] ) ; prevIndices [ i ] = tailIndices [ pos - 1 ] ; tailIndices [ pos ] = i ; } } for ( Integer i = tailIndices [ len - 1 ] ; i >= 0 ; i = prevIndices [ i ] ) res . add ( arr [ i ] ) ; } static void longestBitonic ( Integer [ ] arr1 , Integer n1 , Integer [ ] arr2 , Integer n2 ) { LIS ( arr1 , n1 ) ; Collections . reverse ( res ) ; Collections . reverse ( Arrays . asList ( arr2 ) ) ; LIS ( arr2 , n2 ) ; for ( Integer i = 0 ; i < res . size ( ) ; i ++ ) System . out . print ( res . elementAt ( i ) + " ▁ " ) ; } 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 ) ; } }