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.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <bits/stdc++.h> using namespace std; // Function to find length of Longest Bitonic Subarray in an array int findBitonicSubarray(int A[], int n) { // I[i] stores the length of the longest increasing sub-array // ending at A[i] int I[n + 1]; I[0] = 1; for (int i = 1; i <= n; i++) { I[i] = 1; if (A[i-1] < A[i]) I[i] = I[i-1] + 1; } // D[i] stores the length of the longest decreasing sub-array // starting with A[i] int D[n + 1]; D[n] = 1; for (int i = n - 1; i >= 0; i--) { D[i] = 1; if (A[i] > A[i+1]) D[i] = D[i+1] + 1; } // consider each element as peak and calculate LBS int lbs_len = 1; int beg = 0, end = 0; for (int i = 0; i <= n; i++) { if (lbs_len < I[i] + D[i] - 1) { lbs_len = I[i] + D[i] - 1; beg = i - I[i] + 1; end = i + D[i] - 1; } } // print longest bitonic sub-array printf("The length of longest bitonic sub-array is %d\n", lbs_len); printf("The longest bitonic sub-array is [%d, %d]", beg, end); return lbs_len; } // main function int main() { int A[] = { 3, 5, 8, 4, 5, 9, 10, 8, 5, 3, 4 }; int n = sizeof(A) / sizeof(A[0]); findBitonicSubarray(A, n - 1); return 0; } |

`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++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <stdio.h> #include <stdlib.h> // Function to find length of Longest Bitonic Subarray in an array void findBitonicSubarray(int A[], int n) { int end_index = 0, max_len = 0; int i = 0; while (i + 1 < n) { // check for Longest Bitonic Subarray starting at A[i] // reset length to 1 int len = 1; // run till sequence is increasing while (i + 1 < n && A[i] < A[i + 1]) i++, len++; // run till sequence is decreasing while (i + 1 < n && A[i] > A[i + 1]) i++, len++; // update Longest Bitonic Subarray if required if (len > max_len) { max_len = len; end_index = i; } } // print longest bitonic sub-array printf("The length of longest bitonic sub-array is %d\n", max_len); printf("The longest bitonic sub-array is [%d, %d]", end_index - max_len + 1, end_index); } // main function int main() { int A[] = { 3, 5, 8, 4, 5, 9, 10, 8, 5, 3, 4 }; int n = sizeof(A) / sizeof(A[0]); findBitonicSubarray(A, n); return 0; } |

`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

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)

Thanks a lot Jerome for bringing this issue to our notice. We have corrected the example and also updated the definition. Happy coding 🙂

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.