Consider there is an array a - we need to find the largest prefix of a such that it is good.
The array b of length m is called good, if you can obtain a non-decreasing array c (c1 ≤ c2 ≤ ⋯ ≤ cm) from it, repeating the following operation m times (initially, select either the first or the last element of b, remove it from b, and append it to the end of the array c).
I could only brute force the solution but is there any effective algorithm?
Prove (or at least convince yourself) that a good array cannot have a local minimum. That means that the good array must be unimodal (and a unimodal array is obviously good). In other words, the prefix you are after consists of a non-decreasing leg, followed by a non-increasing one (both could be empty of course).
Such prefix can be found in simple a linear scan.
I hope it is enough to get you started.
Simply saying, the array will be bad when array becames increasing after decreasing when traversing from backside else in any other condition it will be good array.
Eg
4 8 1 2 1
Here in this case array will be good when we exclude first 2 elements.Looking the eg in other way when we are traversing from backside.
1->2 increasing
2->1 decreasing
1->8 increasing---break.. exclude all elements before 8(including 8).
