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

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[0] < arr[1] < ... < 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[0]>=arr[1]){
        return longestBitonic(&arr[1],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[9] ={1, 2, 3, 2, 1, 0, 2, 3, 1};
    int n = sizeof(a)/sizeof(a[0]);
    printf("%d", longestBitonic(a,n));
}

Output

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

People are also reading:

• Subarray with Sum k
• Find the maximum product of two integers in an array
• Move all zeros present in an array to the end
• Program to Find LCM and HCF of two numbers
• Construct a tree from Inorder and Level order traversals
• How to find and remove loops in a Linked List?
• DSA: Graph- Spanning Tree
• Circular Doubly Linked List
• Data Structure Interview Questions
• Find minimum jumps required to reach the destination