You are given an array of n elements you allowed to delete at max one element from provided array. The order of elements remain the same .you are required to maximize the number of subarrays that contain both maximum and minimum element of the resultant array . A subarrays is the sequence of consecutive element of the array
Input
T no of test case
N size of array
N array element
Output
For each test case print one single integer the maximum number of subarrays that contains both maximum and minimum elements of the resultant array
Examples
4
6
7 2 5 4 3 1
7
1 2 3 4 5 6 7
6
2 5 3 2 5 5
4
5 5 5 5
Output
4
1
12
15
Test case 1 explanation
If we delete 1 from the array then the resultant array will be 7 2 5 4 3
So the number of subarrays will contains max 7 and minimum 2 will be 4
[7,2]
[7,2,5]
[7,2,5,4]
[7,2,5,4,3]
I think we can use this logic first point out the first minimum and second minimum ans also the first maximum and second maximum.count the number of subarrays that include (firstmax,firstmin),(firstmax,secondmin),(secondmax,firstmin) return max answer among these.I think this works
how are we handling the cases where there are equal elements in this.
Can you help me with the logic for those ones, I couldn’t solve both of them
Can you give an example
Let’s first write a function to compute the no. of such subarrays if the array is fixed (there are no deletions). Let’s say maximum element(s) is/are max and minimum element(s) is/are min. Now the main problem is handling with multiple instances of maximum and minimum elements. We can use dp to handle this. Say dp[i] is no.of subarrays of array until index i such that the subarray consists of both max and min. Now writing a recursive relation should be easy once you know the indices of previous instance of minimum and previous instance of maximum. So, we can compute this function in O(n).
Now let’s handle deletion case. U might have already realized that you can delete either maximum element or minimum element. If both no.of instances of maximum and no.of instances of minimum are greater than 1, then deletion of any element would only result in decreasing the no.of subarrays consisting min and max (think about it). Hence, we don’t perform deletion in this case. Now, if no.of instances of maximum element = 1, then we delete that element and compute the function for the new array. Same, is the case if no.of instances of minimum element = 1. Finally, find the maximum out of all.
Bro can you share the screen shots including testcases?
You can try to count subarrays that contain both minimum and maximum element either after deleting the firstmin or firstmax. Counting subarrays that contain both minimum and maximum element is O(n) Refer: https://www.geeksforgeeks.org/count-subarrays-which-contains-both-the-maximum-and-minimum-array-element/