# Longest Bitonic subarray in an array

## Given an array, this function will find the length of the longest bitonic subarray in the given 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).

## Algorithm

1. Initialize I[0] to 1 and D[n-1] to 1

2. Creating I[] array
a. Till end of the array ie, i=1 to n, if arr[i] > arr[i-1] then I[i] = I[i-1] + 1.
else, I[i] = 1

3. Creating D[] array
a. From the end of the array ie, i = n-2 till i =0, if arr[i] > arr[i+1] then D[i] = D[i    +1] +1
else, D[i] = 1

4. Find the maximum of I[i] + D[i] -1, it is the length of the longest bitonic subarray.

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

int longestBitonic(int arr[], int n)
{
int I[n], D[n];
int length = 0;
int subarray_start =0, subarray_end = 0;
for (int i = 1; i < n; ++i) //constructing array I[]
{
I[0] = 1;
if(arr[i]>arr[i-1])
{
I[i] = I[i-1] + 1;
}
else
{
I[i] = 1;
}
}
for (int i = n-2; i >=0; --i) //constructing array D[]
{
D[n-1] = 1;
if(arr[i] > arr[i+1])
{
D[i] = D[i+1] +1;
}
else
{
D[i] = 1;
}
}
for (int i = 0; i < n; ++i) //finding maximum length
{
if(I[i] + D[i] -1 > length)
{
length = I[i] + D[i] -1;
subarray_start = i - I[i] +1;
subarray_end = i + D[i] -1;
}

}
cout<<"The length of the longest bitonic subarray is "<<length<<endl;
cout<<"The longest bitonic subarray is from index "<<subarray_start<<" to index "<<subarray_end<<endl;

}
int main()
{
int arr[]= {18, 8, 10, 15, 14, 13};  //creating an array
int n = sizeof(arr)/sizeof(arr[0]); //size of the array
longestBitonic(arr, n);
return 0;
}``````

Scroll to Top