# Longest? ?Bitonic? ?Subarray? ?Problem? ?

Posted in  Vinay Khatri
Last updated on December 4, 2023

1. Problem

An array arr is a bitonic array if and only if: arr .length >= 3 AND There exists some index i (0-indexed) with 0 < i < arr .length - 1 such that:

• arr < arr < ... < arr[i - 1] < arr[i]
• arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Find the length of the longest subarray, which is a bitonic.

## Approach

Without being overly broad, a new mountain of the bitonic array can only begin when the preceding one has finished. This is due to the fact that if it begins before the summit, it will be smaller than a mountain that begins before the peak, and it is impossible to begin after the peak. Calculate the length of the longest mountain ``` arr [ start ``` ``` ] ``` , ``` arr [ start +1],..., arr [ end ``` ``` ] ``` with a starting index ``` start ``` .

If such a mountain existed, the next potential bitonic array would begin at ``` start = end ``` ``` ; ``` if it did not exist, we have either reached the end or we have ``` arr [ start ] >= arr [ start ``` ``` +1] ``` and may begin at ``` start ``` ``` + 1 ``` .

Here’s the diagram for ``` arr = [ 1, 2, 3, 2, 1, 0, 2, 3, 1] ``` ### C++ Programming

```#include<bits/stdc++.h>
using namespace std;
int longestBitonic(vector<int>& a) {
int n=a.size();
int ans=0;
for(int i=1;i<n-1;i++)
{
if(a[i]>a[i-1] && a[i]>a[i+1])
{
int left=i, right=i;
while(left>0 && a[left]>a[left-1])
{
left--;
}
while(right<n-1 && a[right]>a[right+1])
{
right++;
}
ans=max(ans,right-left+1);
}
}
return ans;
}
int main(){
vector<int>v{1, 2, 3, 2, 1, 0, 2, 3, 1};
cout<<longestBitonic(v);
}```

Output

`6`

### C Programming

```#include<stdio.h>
int longestBitonic(int* arr, int n){
if(n<3){return 0;} if(arr>=arr){
return longestBitonic(&arr,n-1);
}
int i=2;
for(;i<n;i++){
if(arr[i]<arr[i-1]){
break;
}
else if(arr[i]==arr[i-1]){
return longestBitonic(&arr[i],n-i);
}
}
int temp=i;
for(;i<n;i++)
{
if(arr[i]>=arr[i-1])
{
break;
}
}
int max=i==temp?0:i;
int ret=longestBitonic(&arr[i-1],n-i+1);
return max>ret?(max>2?max:0):ret;
}
void main(){
int a ={1, 2, 3, 2, 1, 0, 2, 3, 1};
int n = sizeof(a)/sizeof(a);
printf("%d", longestBitonic(a,n));
}
```

`6`

### Python Programming

```def longestBitonic(arr):
res, start = 0, None
for i in range(1, len(arr)):
if arr[i] > arr[i-1] and (i == 1 or arr[i-1] <= arr[i-2]):
start = i - 1
elif arr[i] == arr[i-1]:
start = None
elif arr[i] < arr[i-1] and start is not None:
res = max(res, i - start + 1)
return res

l = [1, 2, 3, 2, 1, 0, 2, 3, 1]
print(longestBitonic(l))
```

Output

`6`