You are given $N$ numbers. Remove contiguous subsequence of those numbers, so the remaining numbers will create a sorted sequence. For example, if the sequence is $5$, $7$, $8$, $2$, $1$, $9$ then we have to remove subsequence $2$, $1$. I am only interested in the minimal amount of numbers removed. If this task wasn't about removing contiguous subsequence, then I would find longest non-decreasing subsequence in O(n log n) and output $N$ - $L$, where $L$ is length of this subsequence.
This task was taken from an old programming competition. I am asking this question, because I'm practising and got really stuck on this one.
If this [wasn't remove one] contiguous subsequence, then I would find longest non-decreasing subsequence
andI tried everything I could
- present, for example, how you tried to use the longest non-decreasing subsequence and knowledge about the elements excluded, and where that got stuck. $\endgroup$