2863. Maximum Length of Semi-Decreasing Subarrays
ArrayStackSortingMonotonic Stack
Hints
Hint 1
First, solve the problem assuming
nums contains distinct values.Hint 2
Make a new array with each element being the pair
(nums[i], i) for every i and call it num_ind.Hint 3
Sort
num_ind in decreasing order.Hint 4
Iterate over
num_ind and store a variable that represents the minimum index (i.e. min of num_ind[i].second) that has been iterated until now. Call it min_indexHint 5
Now if you are currently on pair
(nums[x], x), then ans = max(ans, min_index - x).Hint 6
Now try to remove the first assumption.
Preparing judge…