Find Longest Bitonic Subarray in an array

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.

Example Solution

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.

Contributed by Murat Sütunç