Longest increasing sequence possible by the boundary elements of an Array | C ++ program for the above approach ; 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
#include <iostream> NEW_LINE #include <vector> NEW_LINE using namespace std ; void findMaxLengthSequence ( int N , int arr [ 4 ] ) { int rightmost_element = -1 ; int i = 0 ; int j = N - 1 ; vector < int > sequence ; while ( i <= j ) { if ( arr [ i ] > arr [ j ] ) { if ( arr [ j ] > rightmost_element ) { sequence . push_back ( arr [ j ] ) ; rightmost_element = arr [ j ] ; j -- ; } else if ( arr [ i ] > rightmost_element ) { sequence . push_back ( arr [ i ] ) ; rightmost_element = arr [ i ] ; i ++ ; } else break ; } else if ( arr [ i ] < arr [ j ] ) { if ( arr [ i ] > rightmost_element ) { sequence . push_back ( arr [ i ] ) ; rightmost_element = arr [ i ] ; i ++ ; } else if ( arr [ j ] > rightmost_element ) { sequence . push_back ( 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_back ( arr [ i ] ) ; rightmost_element = arr [ i ] ; i ++ ; } break ; } else { sequence . push_back ( arr [ i ] ) ; int k = i + 1 ; vector < int > max_left ; while ( k < j && arr [ k ] > arr [ k - 1 ] ) { max_left . push_back ( arr [ k ] ) ; k ++ ; } int l = j - 1 ; vector < int > max_right ; while ( l > i && arr [ l ] > arr [ l + 1 ] ) { max_right . push_back ( arr [ l ] ) ; l -- ; } if ( max_left . size ( ) > max_right . size ( ) ) for ( int element : max_left ) sequence . push_back ( element ) ; else for ( int element : max_right ) sequence . push_back ( element ) ; break ; } } } for ( int element : sequence ) printf ( " % d ▁ " , element ) ; } int main ( ) { int N = 4 ; int arr [ ] = { 1 , 3 , 2 , 1 } ; findMaxLengthSequence ( N , arr ) ; }