Longest increasing sequence possible by the boundary elements of an Array | Function to find longest strictly increasing sequence using boundary elements ; Maintains rightmost element in the sequence ; Pointer to start of array ; Pointer to end of array ; Stores the required sequence ; Traverse the array ; If arr [ i ] > arr [ j ] ; If arr [ j ] is greater than rightmost element of the sequence ; Push arr [ j ] into the sequence ; Update rightmost element ; Push arr [ i ] into the sequence ; Update rightmost element ; If arr [ i ] < arr [ j ] ; If arr [ i ] > rightmost element ; Push arr [ i ] into the sequence ; Update rightmost element ; If arr [ j ] > rightmost element ; Push arr [ j ] into the sequence ; Update rightmost element ; If arr [ i ] is equal to arr [ j ] ; If i and j are at the same element ; If arr [ i ] > rightmostelement ; Push arr [ j ] into the sequence ; Update rightmost element ; Traverse array from left to right ; Stores the increasing sequence from the left end ; Traverse array from left to right ; Push arr [ k ] to max_left vector ; Traverse the array from right to left ; Stores the increasing sequence from the right end ; Traverse array from right to left ; Push arr [ k ] to max_right vector ; If size of max_left is greater than max_right ; Push max_left elements to the original sequence ; Otherwise ; Push max_right elements to the original sequence ; Print the sequence ; Driver code ; Print the longest increasing sequence using boundary elements
function findMaxLengthSequence ( N , arr ) { let rightmost_element = - 1 ; let i = 0 ; let j = N - 1 ; let sequence = [ ] ; while ( i <= j ) { if ( arr [ i ] > arr [ j ] ) { if ( arr [ j ] > rightmost_element ) { sequence . push ( arr [ j ] ) ; rightmost_element = arr [ j ] ; j -- ; } else if ( arr [ i ] > rightmost_element ) { sequence . push ( arr [ i ] ) ; rightmost_element = arr [ i ] ; i ++ ; } else break ; } else if ( arr [ i ] < arr [ j ] ) { if ( arr [ i ] > rightmost_element ) { sequence . push ( arr [ i ] ) ; rightmost_element = arr [ i ] ; i ++ ; } else if ( arr [ j ] > rightmost_element ) { sequence . push ( arr [ j ] ) ; rightmost_element = arr [ j ] ; j -- ; } else break ; } else if ( arr [ i ] == arr [ j ] ) { if ( i == j ) { if ( arr [ i ] > rightmost_element ) { sequence . push ( arr [ i ] ) ; rightmost_element = arr [ i ] ; i ++ ; } break ; } else { sequence . push ( arr [ i ] ) ; let k = i + 1 ; let max_left = [ ] ; while ( k < j && arr [ k ] > arr [ k - 1 ] ) { max_left . push ( arr [ k ] ) ; k ++ ; } let l = j - 1 ; let max_right = [ ] ; while ( l > i && arr [ l ] > arr [ l + 1 ] ) { max_right . push ( arr [ l ] ) ; l -- ; } if ( max_left . length > max_right . length ) for ( let element = 0 ; element < max_left . length ; element ++ ) sequence . push ( max_left [ element ] ) ; else for ( let element = 0 ; element < max_right . length ; element ++ ) sequence . push ( max_right [ element ] ) ; break ; } } } for ( let element = 0 ; element < sequence . length ; element ++ ) document . write ( sequence [ element ] + " " ) ; } let N = 4 ; let arr = [ 1 , 3 , 2 , 1 ] ; findMaxLengthSequence ( N , arr ) ;