Remove contiguous subsequence so the remaining numbers will created a sorted sequence

Question

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.

Answer 1

Let the original sequence be $a_1,\ldots,a_n$. After removing a contiguous subsequence $a_{i+1},\ldots,a_{j-1}$, we are left with $a_1,\ldots,a_i,a_j,\ldots,a_n$ (possibly $i = 0$ or $j = n+1$). In particular, if $a_1 \leq a_2 \leq \cdots \leq a_I > a_{I+1}$ then $i \leq I$, and if $a_{J-1} > a_J \leq a_{J+1} \leq \cdots \leq a_n$ then $j \geq J$. In other words, we can remove all elements $a_{J+1},\ldots,a_{I-1}$. Renaming elements, we are left with two non-decreasing sequences $$a_1,\ldots,a_s,b_1,\ldots,b_t.$$ Merge both sequences, and consider all places in the merged sequence in which a $b$-element follows an $a$-element, say $a_i,b_j$. This corresponds to the sorted sequence $a_1,\ldots,a_i,b_j,\ldots,b_t$ of length $i+t-j+1$. Go over all such places and choose the one maximizing the length of the corresponding sequence. (You also need to consider some corner cases, which I leave to you.)

This algorithm runs in linear time, and so is asymptotically optimal.