You are given an array of n numbers
Find the longest consecutive subarray so that The Last and First member of the sub array is Neither the Smallest or the Biggest member of That subarray (not the entire array)
for example
1 3 2 4 6 5 7
the sub array [3, 2, 4, 6, 5]
in this subarray the smallest member is 2 and the biggest member is 6, the first member is 3 which is not equal to 2 or 6, the last member 5 is not equal to 2 or 6 either so this is a valid subarray, so you cout 2 6 (the l and r of the subarray)
The goal is to find a Valid subarray
the second Goal is to find the Biggest valid subarray
the numbers are from 0 up to 1e9 and n is from from 1 up to 2*1e5
My strategy is to make a two vector of vectors, saving the numbers sorted from index 0 up to i so you can always know the smallest and biggest member of each subarray and then just do a sliding window algorithm.
I believe this problem can be directly solved by removing either the minimum or maximum element from both ends of the array.
If someone has an easier approach, please share. I think we can do d&c. Suppose we split a segment in the middle, and the "optimal" segment lies over this split. Then it consists of a suffix of the left segment, and a prefix of the right segment. We have 2 cases:
One of the endpoints (left or right) is neither the smallest nor the largest element of the corresponding half.
The endpoints are the largest (but not smallest) and the smallest (but not largest) in their halfs.
For the first case, we iterate over the other side, and we only need to check the furthest prefix/suffix on the other side that satisfies the first case.
For the second case, we can do 2 pointers approach over the suffixes/prefixes that satisfy this case, and keep track of the furthest suffix/prefix that is still (maybe) possible. For example, if right endpoint is minimum in its half, and left endpoint is maximum, and H is the largest value in the right half, then from the suffix maxima on the left side, we point to the largest one that is strictly less than H. Then we need to check whether the minimum on the left side is less than the right endpoint.
This is O(n log(n)). I feel like there might be a way easier solution, so please tell me if so.
First choose all elements. If one endpoint is the smallest or the largest element, then we cannot let it is not by moving another endpoint. Then we can only remove this endpoint. Repeating this procedure is OK.
This problem is basically the same as 1793C - Даша и поиски
But in this problem it is not mentioned that the numbers are permutaions of n, it can be any random n numbers.
I think original solution approach should still work even if they're not permutations, though might not be able to work in $$$O(n)$$$
Ah no see the problem is in dora and the search its a permutation
if either corner is mn or mx you can just ++ or -- the mx or min to find the Next mx or min
because if till the current index the mx stayed valid and now it falls of the l, we can mx++ because we can prove the new max is to the right of the array, so all we got to do is also check if for our R its also still to the right of the array, no need to Loop to see what is the min or max to the right
best case for this question is n(log n) because n is not possible
There’s not much difference, the core idea is same, it’s just the way we maintain the min and max in the subarray is different(like multiset)
ye but the way you save min and max can go up to n^2, i was looking for the best one which rn is n log n
Using multiset can work in $$$O(n\log{n})$$$
Nice problem btw