The Interview Question Today#13(8-3-19)

Question:
Find longest bitonic subarray in an array

Example:

Input: A[] = {12, 4, 78, 90, 45, 23}

Output: the maximum length bitonic subarray is {4, 78, 90, 45, 23} which is of length 5.



Approach:

Let us consider the array {12, 4, 78, 90, 45, 23} to understand the solution.
1) Construct an auxiliary array inc[] from left to right such that inc[i] contains the length of the nondecreasing subarray ending at arr[i].
For 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 the 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.


C program:
#include <stdio.h>

// Function to find length of Longest Bitonic Subarray in an array
int findBitonicSubarray(int A[], int n)
{
// I[i] stores the length of the longest increasing sub-array ending at A[i]
int I[n + 1],i;
I[0] = 1;
for ( i = 1; i <= n; i++) {
I[i] = 1;
if (A[i-1] < A[i])
I[i] = I[i-1] + 1;
}

// D[i] stores the length of the longest decreasing sub-array starting with A[i]
int D[n + 1];
D[n] = 1;
for ( i = n - 1; i >= 0; i--) {
D[i] = 1;
if (A[i] > A[i+1])
D[i] = D[i+1] + 1;
}

int lbs_len = 1;
int beg = 0, end = 0;

for ( i = 0; i <= n; i++)
{
if (lbs_len < I[i] + D[i] - 1)
{
lbs_len = I[i] + D[i] - 1;
beg = i - I[i] + 1;
end = i + D[i] - 1;
}
}

printf("The length of longest bitonic sub-array is %d\n", lbs_len);
printf("The longest bitonic sub-array is [%d...... %d]", beg, end);

return lbs_len;
}

// main function
int main(void)
{
int arr[100] ;
int n,i;
    printf("Enter the Number of Elements present: ");
    scanf("%d",&n);
    printf("\nEnter the values of Elements");
    for(i=0;i<n;i++)
    {
        printf("\nElements %d:",i+1);
        scanf("%d",&arr[i]);
    }

findBitonicSubarray(arr,n - 1);

return 0;
}

Output:
Enter the Number of Elements present: 5

Enter the values of Elements
Elements 1:2

Elements 2:3

Elements 3:4

Elements 4:2

Elements 5:1
The length of longest bitonic sub-array is 5
The longest bitonic sub-array is [0...... 4]