Find longest bitonic sequence such that increasing and decreasing parts are from two different arrays | C # to find largest bitonic sequence ; Utility Binary search ; Reverse array ; 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
using System ; using System . Collections . Generic ; class GFG { static List < int > res = new List < int > ( ) ; 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 ; } 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 ; } static void LIS ( int [ ] arr , int n ) { 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 ; 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 . Add ( arr [ i ] ) ; } static void longestBitonic ( int [ ] arr1 , int n1 , int [ ] arr2 , int n2 ) { LIS ( arr1 , n1 ) ; res . Reverse ( ) ; arr2 = reverse ( arr2 ) ; LIS ( arr2 , n2 ) ; for ( int i = 0 ; i < res . Count ; i ++ ) Console . Write ( res [ i ] + " ▁ " ) ; } 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 ) ; } }