# Find Longest Bitonic Subarray in an array

The longest bitonic subarray problem is to find a subarray of a given sequence in which the subarray’s elements are first sorted in in increasing order, then in decreasing order, and the subarray is as long as possible. Strictly ascending or descending subarrays are also accepted.

For example,

Longest Bitonic Subarray of sequence { 3, 5, 8, 4, 5, 9, 10, 8, 5, 3, 4 } is
{ 4, 5, 9, 10, 8, 5, 3 }

For sequences sorted in increasing or decreasing order, the output is same as the input sequence. i.e.

[1, 2, 3, 4, 5] —> [1, 2, 3, 4, 5]
[5, 4, 3, 2, 1] —> [5, 4, 3, 2, 1]

The idea is to maintain two arrays I[] and D[]

• I[i] stores the length of the longest increasing sub-array ending at arr[i]

• D[i] stores the length of the longest decreasing sub-array starting from arr[i]

Finally, length of Longest Bitonic Subarray is maximum among all (I[i] + D[i] – 1). We can also keep track of two end-points of Longest Bitonic Subarray found so far to print LBS.

## C

Output:

The length of longest bitonic sub-array is 7
The longest bitonic sub-array is [3, 9]

## Java

Output:

The length of longest bitonic sub-array is 7
The longest bitonic sub-array is [3, 9]

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

We can solve this problem without using extra space. The idea is to check for longest bitonic subarray starting at A[i]. If longest bitonic subarray starting at A[i] ends at A[j], the trick is to skip all elements between i and j as longest bitonic subarray starting from them will have less length. So, next we check for longest bitonic subarray starting at A[j]. We continue this process till end of array is reached and also keep track of longest bitonic subarray found so far.

## C

Output:

The length of longest bitonic sub-array is 7
The longest bitonic sub-array is [3, 9]

## Java

Output:

The length of longest bitonic sub-array is 7
The longest bitonic sub-array is [3, 9]

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

Exercise: Find an element in the array before which all the elements are smaller and after which all are greater.     (3 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest
Jerome Labonte

The definition of bitonic subarray should be more precise. According to what is currently written, one would think that the longest bitonic subarray in {4, 3, 2, 1, 2, 1} is {1, 2, 1} but your solutions returns {4, 3, 2, 1}. That means that strictly ascending or descending subarrays are also accepted. The current explanation only covers when the whole array is descending or ascending. Guest
Jerome Labonte

If I understood correctly and if the answer is right, the first statement should be : Longest Bitonic Subarray of sequence { 3, 5, 8, 4, 5, 9, 10, 8, 5, 3, 4 } is
{ 4, 5, 9, 10, 8, 5, 3 } (without the 4 at the end) Guest
Cristiano

Why pass n to findBitonicSubarray? Furthermore, pass n-1. That just makes the code more confusing if you are thinking in “0-indexed arrays” mind. Just Calculate n in findBitonicSubarray.

P.S.: Talking about Java. Perhaps it is needed for C