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$
4
  • 2
    $\begingroup$ Can you share the link to the problem ? $\endgroup$
    – mrk
    Commented Jan 13, 2016 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$ Commented Jan 13, 2016 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
    Commented Jan 13, 2016 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.
    Commented Jan 14, 2016 at 0:00

1 Answer 1

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$
2
  • 1
    $\begingroup$ Does this algorithm always removes minimal amount of numbers? $\endgroup$ Commented Jan 13, 2016 at 23:07
  • $\begingroup$ @user4201961 Yes, that's the claim. $\endgroup$ Commented Jan 14, 2016 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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