Can u help me understand the below q and solve this using cpp

#1

You are provided n numbers of array. You need to find the maximum length of bitonic subarray. A subarray A[i … j] is biotonic if there is a k with i <= k <= j such that A[i] <= A[i + 1] … <= A[k] >= A[k + 1] >= … A[j – 1] > = A[j] i.e subarray is first increasing and then decreasing or entirely increasing or decreasing.
Input Format

First line contains integer t which is number of test case. For each test case, it contains an integer n which is the size of array and next line contains n space separated integers.
Constraints

1<=t<=100 1<=n<=1000000
Output Format

Print the maximum length.
Sample Input

2
6
12 4 78 90 45 23
4
40 30 20 10

Sample Output

5
4

Explanation

ForMaximum length = 4, 78, 90, 45, 23

#2

Hey @Kash-Moulik-3715574511847721
Refer to this to understand the problem : https://www.youtube.com/watch?v=k4vMVTp6AuI&feature=youtu.be

We create two arrays - ‘inc’ and ‘dec’

  • inc[i] stores the length of increasing subarray till i.
  • dec[i] stores the length of decreasing subarray starting from index i.
  • Doing so gives us the length of increasing and decreasing subarray at each index in O(n) time.
  • We calculate the length of the longest bitonic subarray by finding the maximum inc[i] + dec[i] - 1
  • We subtract one since the current element at ith index is included in both the increasing and decreasing subarray lengths.

Algorithm

  • Initialize inc[0] to 1 and dec[n-1] to 1
  • Creating inc[] array
    a. Till end of the array ie, i=1 to n, if arr[i] > arr[i-1] then inc[i] = inc[i-1] + 1. else, inc[i] = 1
  • Creating dec[] array
    a. From the end of the array ie, i = n-2 till i =0, if arr[i] > arr[i+1] then dec[i] = dec[i+1] +1 else, dec[i] = 1

Try this question on ur own first now before asking for solution.

#3

ok i tried now I like to see ur way of approch for soln in cpp

#4

Hey @Kash-Moulik-3715574511847721

int bitonic_Subarray(int a[], int n){
        int *inc=new int[1000000];
	int *dec=new int[1000000];
	inc[0] = 1;
	dec[n-1] = 1;
    for(int i=1; i<=n-1; i++){
		inc[i] = (a[i] >= a[i-1]) ? inc[i-1] + 1 : 1;  
	}
	for(int i=n-2; i>=0; i--){
		dec[i] = (a[i] <= a[i+1]) ? dec[i+1] + 1 : 1;  
	}
	int max= inc[0] + dec[0] - 1;
	for(int i=1; i<=n-1; i++){
        if(inc[i] + dec[i] - 1 > max){
			max = inc[i] + dec[i] -1;
		}
	}
	return max;
}
#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.