The Longest Bitonic Subarray (LBS) problem is to find a subarray of a given sequence in which the subarray’s elements are first sorted 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 the 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 the 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]

Practice this problem

The problem differs from the problem of finding the longest bitonic subsequence. Unlike subsequences, subarrays are required to occupy consecutive positions within the original array.

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

• `I[i]` store the length of the longest increasing subarray, ending at `arr[i]`.
• `D[i]` store the length of the longest decreasing subarray, starting from `arr[i]`.

Finally, the length of the longest bitonic subarray is maximum among all `I[i] + D[i] - 1`. We can also keep track of two endpoints of the longest bitonic subarray found so far to print LBS. The algorithm can be implemented as follows in C, Java, and Python:

## C

Output:

The length of the longest bitonic subarray is 7
The longest bitonic subarray indices is [3, 9]

## Java

Output:

The length of the longest bitonic subarray is 7
The longest bitonic subarray indices is [3, 9]

## Python

Output:

The length of the longest bitonic subarray is 7
The longest bitonic subarray is [4, 5, 9, 10, 8, 5, 3]

The time complexity of the above solution is O(n) and requires O(n) extra space, where `n` is the size of the input.

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

Following is the C, Java, and Python implementation based on the above idea:

## C

Output:

The length of the longest bitonic subarray is 7
The longest bitonic subarray indices is [3, 9]

## Java

Output:

The length of the longest bitonic subarray is 7
The longest bitonic subarray indices is [3, 9]

## Python

Output:

The length of the longest bitonic subarray is 7
The longest bitonic subarray is [4, 5, 9, 10, 8, 5, 3]

The time complexity of the above solution is O(n) and doesn’t require any extra space.

Exercise: Find an array element before which all the items are smaller and after which all are greater.