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

Posted in

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

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[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:

    Leave a Comment on this Post

    0 Comments