Find longest bitonic sequence such that increasing and decreasing parts are from two different arrays | Python3 to find largest bitonic sequence such that ; utility Binary search ; function to find LIS in reverse form ; leN = 1 it will always poto 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 program
res = [ ] NEW_LINE def GetCeilIndex ( arr , T , l , r , key ) : NEW_LINE INDENT while ( r - l > 1 ) : NEW_LINE INDENT m = l + ( r - l ) // 2 ; NEW_LINE if ( arr [ T [ m ] ] >= key ) : NEW_LINE INDENT r = m NEW_LINE DEDENT else : NEW_LINE INDENT l = m NEW_LINE DEDENT DEDENT return r NEW_LINE DEDENT def LIS ( arr , n ) : NEW_LINE INDENT for i in range ( 1 , n ) : NEW_LINE INDENT if ( arr [ i ] < arr [ tailIndices [ 0 ] ] ) : NEW_LINE INDENT tailIndices [ 0 ] = i NEW_LINE DEDENT elif ( arr [ i ] > arr [ tailIndices [ leN - 1 ] ] ) : NEW_LINE INDENT prevIndices [ i ] = tailIndices [ leN - 1 ] NEW_LINE tailIndices [ leN ] = i NEW_LINE leN += 1 NEW_LINE DEDENT else : NEW_LINE INDENT pos = GetCeilIndex ( arr , tailIndices , - 1 , leN - 1 , arr [ i ] ) NEW_LINE prevIndices [ i ] = tailIndices [ pos - 1 ] NEW_LINE tailIndices [ pos ] = i NEW_LINE DEDENT DEDENT i = tailIndices [ leN - 1 ] NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT res . append ( arr [ i ] ) NEW_LINE i = prevIndices [ i ] NEW_LINE DEDENT DEDENT def longestBitonic ( arr1 , n1 , arr2 , n2 ) : NEW_LINE INDENT global res NEW_LINE LIS ( arr1 , n1 ) NEW_LINE res = res [ : : - 1 ] NEW_LINE arr2 = arr2 [ : : - 1 ] NEW_LINE LIS ( arr2 , n2 ) NEW_LINE for i in res : NEW_LINE INDENT print ( i , end = " ▁ " ) NEW_LINE DEDENT DEDENT arr1 = [ 1 , 2 , 4 , 3 , 2 ] NEW_LINE arr2 = [ 8 , 6 , 4 , 7 , 8 , 9 ] NEW_LINE n1 = len ( arr1 ) NEW_LINE n2 = len ( arr2 ) NEW_LINE longestBitonic ( arr1 , n1 , arr2 , n2 ) ; NEW_LINE