3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Can you share the link to the problem ? $\endgroup$ – saadtaame Jan 13 '16 at 14:32
  • $\begingroup$ 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) $\endgroup$ – user4201961 Jan 13 '16 at 21:27
  • 1
    $\begingroup$ 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. $\endgroup$ – greybeard Jan 13 '16 at 21:36
  • 1
    $\begingroup$ 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! $\endgroup$ – D.W. Jan 14 '16 at 0:00
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Does this algorithm always removes minimal amount of numbers? $\endgroup$ – user4201961 Jan 13 '16 at 23:07
  • $\begingroup$ @user4201961 Yes, that's the claim. $\endgroup$ – Yuval Filmus Jan 14 '16 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.