### Maximum length of Bitonic Subarray

If we take an array of length N which contains N positive elements than **bitonic subarray** is a subarray having **n** positive integers where **n<=N** in such a way that all the integers follow one of the sequences:

- All the integers of subarray are in increasing order.
- All the integers of the subarray are in decreasing order.
- All the integers are arranged in such a manner that they are first increasing at a particular index and after that index they are continuously decreasing.

**Example :-**

Input : array[] = {2, 1, 3, 2, 1} Output : 4 [1, 3, 2, 1] Input : array[]={12, 4, 78, 90, 45, 23} Output : 5 [4, 78, 90, 45, 23] Input : array[] = {3, 5, 2, 9, 50, 75, 60, 12} left[] = {1, 2, 1, 2, 3, 4, 1, 1} right[] = {1, 2, 1, 1, 1, 3, 2, 1} left[i]+right[i]-1 = {1, 3, 1, 2, 3, 6, 2, 1} max(left[i]+right[i]-1)=maximum length of bitonic subarray =6 Bitonic Subarray = {2, 9, 50, 75, 60, 12} Output : 6

**Step 1**: Construct an auxiliary array left [] (which is of same length as input array) and iterate over the input array from left to right in such a way that every index of left [] contains the length of subarray which is non-decreasing from its left-side elements.

**Step 2**: Construct an auxiliary array right [] (which is of same length as input array) and iterate over the input array from right to left in such a way that every index of right [] contains the length of subarray which is non-increasing from its right-side elements.

**Step 3**: Once we have left [] and right [] arrays all we need to do is find the maximum value of (left[i]+right[i]-1).

**Explanation :-**

- Take left[0] = 1 and right[N-1]=1 [where N is the length of the input array i.e. 8 in above example].
- We do left[i] = left[i]+1 when arr[i]>arr[i-1] [where 1<=i <N]. As left[] array contains the length of non-decreasing subarray from left side or we can say length of subarray which is in ascending order from left side. As shown in fig. left[5] = 4 that means there is subarray of length 4 including arr[5] element in input array which are in non-decreasing order. {2, 9, 50, 75} is subarray from index 2 to 5 which is non-decreasing subarray from left to right.
- We do right[i] = right[i]+1 when arr[i]>arr[i-1] [where N-1 > i >=0]. As right[] array contains the length of non-increasing subarray. As shown in fig. right[5] = 3 that means there is subarray of length 3 including arr[5] element in input array which are in non-decreasing order. {70, 60, 12} is subarray from index 5 to 7 which is non-increasing subarray from right to left.
- Maximum of right[i]+left[i]-1 [where 0<=i<N]. We can subtract 1 from right[i]+left[i] because left array contains the length of non-decreasing elements of left side from index i of input array and right array contains the length of non-increasing elements of right side from index i of input array. So, index i elements included twice in length that’s why we subtract it once to get the accurate length.

Click here to check C++ implementation of maximum length of bitonic subarray

CommentsNo comment yet.