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.

 

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, 4 }

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++ implementation –
 

Download   Run Code

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++ implementation –
 

Download   Run Code

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.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz