Longest Bitonic subarray in an array

Longest Bitonic subarray in an array

Array is said to be bitonic if the elements in the array are first increasing and then decreasing. A sequence sorted in increasing order considerd bitonic with decreasing part as empty. Smilarly,  a sequence sorted in deccreasing order considerd bitonic with increasing part as empty.

Example 1

INPUT:
arr[] = {4, 7, 9, 20, 13}

OUTPUT:
5
The above array is bitonic as the elements are first increasing till 20 and then decreasing

Example 2

INPUT:
arr[] = {18, 8, 10, 15, 14, 13}

OUTPUT:
5
The longest bitonic subarray is of length 5 and the bitonic subarray is {8, 10, 15, 14, 13}

Time Complexity: O(n)
In this method the main idea is to maintain two arrays I[] and D[]
a. I[i] stores the length of the longest increasing subarray from left to right ending at arr[i]
b. D[i] stores the length of the longest decreasing subarray from right to left starting at arr[i]
c. maximum length of the bitonic subarray is maximum of (I[i]+D[i]-1).

Read full article from Longest Bitonic subarray in an array