Maximum Length Bitonic Subarray | Set 1 (O(n) time and O(n) space)

Question - 

Given an array A[0 … n-1] containing n positive integers, a subarray A[i … j] is bitonic if there is a k with i <= k <= j such that A[i] <= A[i + 1] … = A[k + 1] >= .. A[j – 1] > = A[j]. Write a function that takes an array as argument and returns the length of the maximum length bitonic subarray.
Expected time complexity of the solution is O(n)

Examples - 
1) A[] = {12, 4, 78, 90, 45, 23}, the maximum length bitonic subarray is {4, 78, 90, 45, 23} which is of length 5.

2) A[] = {20, 4, 1, 2, 3, 4, 2, 10}, the maximum length bitonic subarray is {1, 2, 3, 4, 2} which is of length 5.

Extreme Examples -

Input : A[] = {10},

the single element is bitnoic, so output is 1.

Input : A[] = {10, 20, 30, 40}, 

the complete array itself is bitonic, so output is 4.

Input : A[] = {40, 30, 20, 10}, 

the complete array itself is bitonic, so output is 4.

Solution - 

Let us consider the array {12, 4, 78, 90, 45, 23} to understand the soultion.
1) Construct an auxiliary array inc[] from left to right such that inc[i] contains length of the nondecreaing subarray ending at arr[i].
For A[] = {12, 4, 78, 90, 45, 23}, inc[] is {1, 1, 2, 3, 1, 1}

2) Construct another array dec[] from right to left such that dec[i] contains length of nonincreasing subarray starting at arr[i].
For A[] = {12, 4, 78, 90, 45, 23}, dec[] is {2, 1, 1, 3, 2, 1}.

3) Once we have the inc[] and dec[] arrays, all we need to do is find the maximum value of (inc[i] + dec[i] – 1).
For {12, 4, 78, 90, 45, 23}, the max value of (inc[i] + dec[i] – 1) is 5 for i = 3

Implementation - 

#include<iostream>

using namespace std;

void print(int arr[],int n)

{

    for(int i=0;i<n;i++)

        cout<<arr[i]<<" ";

        cout<<endl;

}

void bitonic(int arr[],int n)

{

    int inc[n],dec[n];

    inc[0]=1;

    int flag=1;

    // for for increasing array

    for(int i=1;i<n;i++){

        if(arr[i-1]<arr[i]){

            inc[i]=++flag;

        }

        else{

            flag=1;

            inc[i]=flag;

        }

    }   

    //for for decreasing array

    flag=1;

    dec[n-1]=1;

    for(int i=n-2;i>=0;i--){

        if(arr[i]>arr[i+1]){

            dec[i]=++flag;

        }

        else{

            flag=1;

            dec[i]=flag;

        }

    }

    //find final answer

    int max=inc[0]+dec[0]-1;

    for(int i=0;i<n;i++){

            if(inc[i]+dec[i]-1>max)

            max=inc[i]+dec[i]-1;

    }

    cout<<"Length of max bitocin is : "<<max<<endl;

}

int main()

{

    int n;

    cout<<"Enter the number of elements : ";cin>>n;

    int arr[n];

    cout<<"Enter elements : "<<endl;

    for(int i=0;i<n;i++)

    cin>>arr[i];

    bitonic(arr,n);

}

Time complexity - O(n)

Extra space - O(3*n)