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

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.

• Can you share the link to the problem ? – saadtaame Jan 13 '16 at 14:32
• If I am asking this question, then it means that I tried everything I could :P. The only thing I can do is brute-force in O(n^2) – user4201961 Jan 13 '16 at 21:27
• If this [wasn't remove one] contiguous subsequence, then I would find longest non-decreasing subsequence and I 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. – greybeard Jan 13 '16 at 21:36
• There's always some things you can try, and tell us about! What's the fastest algorithm you were able to come up with? Have you considered any special cases of the problem, and what were the best techniques for each? Did you try working through some examples to see if you can spot any patterns? What algorithm design paradigms have you tried applying, and what barrier did you hit for each? There's always more you can try and share than "I got really stuck". Be prepared to put in a bunch of effort before asking. Showing us what you tried helps you and others! – D.W. Jan 14 '16 at 0:00

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.)