A sequence is called Bitonic if it is first increasing, then decreasing. In other words, an array arr[0..n-i]
is Bitonic if there exists an index i
where 0 <= i <= n-1
such that
x0 <= x1 <= … <= xi
and
xi >= xi+1 >= … >= xn-1
A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty. A rotation of Bitonic Sequence is also bitonic.
Given an array of integers, find the longest bitonic subarray and return it.
Let array arr
equal to [ 3, 5, 8, 4, 5, 9, 10, 8, 5, 3, 4 ]
. The longest Bitonic subarray is [ 4, 5, 9, 10, 8, 5, 3 ]
. The solution should return this array.