human
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"
Solution in Python:
assistant
#Here is code to longest increasing sequence possible by the boundary elements of an Array and the other steps required.
 def findMaxLengthSequence ( N , arr ) :
	rightmost_element = - 1
	i = 0
	j = N - 1
	sequence = [ ]
	while ( i <= j ) :
		if ( arr [ i ] > arr [ j ] ) :
			if ( arr [ j ] > rightmost_element ) :
				sequence . append ( arr [ j ] )
				rightmost_element = arr [ j ]
				j -= 1
			elif ( arr [ i ] > rightmost_element ) :
				sequence . append ( arr [ i ] )
				rightmost_element = arr [ i ]
				i += 1
			else :
				break
		elif ( arr [ i ] < arr [ j ] ) :
			if ( arr [ i ] > rightmost_element ) :
				sequence . append ( arr [ i ] )
				rightmost_element = arr [ i ]
				i += 1
			elif ( arr [ j ] > rightmost_element ) :
				sequence . append ( arr [ j ] )
				rightmost_element = arr [ j ]
				j -= 1
			else :
				break
		elif ( arr [ i ] == arr [ j ] ) :
			if ( i == j ) :
				if ( arr [ i ] > rightmost_element ) :
					sequence . append ( arr [ i ] )
					rightmost_element = arr [ i ]
					i += 1
				break
			else :
				sequence . append ( arr [ i ] )
				k = i + 1
				max_left = [ ]
				while ( k < j and arr [ k ] > arr [ k - 1 ] ) :
					max_left . append ( arr [ k ] )
					k += 1
				l = j - 1
				max_right = [ ]
				while ( l > i and arr [ l ] > arr [ l + 1 ] ) :
					max_right . append ( arr [ l ] )
					l -= 1
				if ( len ( max_left ) > len ( max_right ) ) :
					for element in max_left :
						sequence . append ( element )
				else :
					for element in max_right :
						sequence . append ( element )
				break
	for element in sequence :
		print ( element , end = " ▁ " )
if __name__ == ' _ _ main _ _ ' :
	N = 4
	arr = [ 1 , 3 , 2 , 1 ]
	findMaxLengthSequence ( N , arr )