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
def findMaxLengthSequence ( N , arr ) : NEW_LINE INDENT rightmost_element = - 1 NEW_LINE i = 0 NEW_LINE j = N - 1 NEW_LINE sequence = [ ] NEW_LINE while ( i <= j ) : NEW_LINE INDENT if ( arr [ i ] > arr [ j ] ) : NEW_LINE INDENT if ( arr [ j ] > rightmost_element ) : NEW_LINE INDENT sequence . append ( arr [ j ] ) NEW_LINE rightmost_element = arr [ j ] NEW_LINE j -= 1 NEW_LINE DEDENT elif ( arr [ i ] > rightmost_element ) : NEW_LINE INDENT sequence . append ( arr [ i ] ) NEW_LINE rightmost_element = arr [ i ] NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT elif ( arr [ i ] < arr [ j ] ) : NEW_LINE INDENT if ( arr [ i ] > rightmost_element ) : NEW_LINE INDENT sequence . append ( arr [ i ] ) NEW_LINE rightmost_element = arr [ i ] NEW_LINE i += 1 NEW_LINE DEDENT elif ( arr [ j ] > rightmost_element ) : NEW_LINE INDENT sequence . append ( arr [ j ] ) NEW_LINE rightmost_element = arr [ j ] NEW_LINE j -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT elif ( arr [ i ] == arr [ j ] ) : NEW_LINE INDENT if ( i == j ) : NEW_LINE INDENT if ( arr [ i ] > rightmost_element ) : NEW_LINE INDENT sequence . append ( arr [ i ] ) NEW_LINE rightmost_element = arr [ i ] NEW_LINE i += 1 NEW_LINE DEDENT break NEW_LINE DEDENT else : NEW_LINE INDENT sequence . append ( arr [ i ] ) NEW_LINE k = i + 1 NEW_LINE max_left = [ ] NEW_LINE while ( k < j and arr [ k ] > arr [ k - 1 ] ) : NEW_LINE INDENT max_left . append ( arr [ k ] ) NEW_LINE k += 1 NEW_LINE DEDENT l = j - 1 NEW_LINE max_right = [ ] NEW_LINE while ( l > i and arr [ l ] > arr [ l + 1 ] ) : NEW_LINE INDENT max_right . append ( arr [ l ] ) NEW_LINE l -= 1 NEW_LINE DEDENT if ( len ( max_left ) > len ( max_right ) ) : NEW_LINE INDENT for element in max_left : NEW_LINE INDENT sequence . append ( element ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT for element in max_right : NEW_LINE INDENT sequence . append ( element ) NEW_LINE DEDENT DEDENT break NEW_LINE DEDENT DEDENT DEDENT for element in sequence : NEW_LINE INDENT print ( element , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 4 NEW_LINE arr = [ 1 , 3 , 2 , 1 ] NEW_LINE findMaxLengthSequence ( N , arr ) NEW_LINE DEDENT