Given an array of N integers, how can you find M elements to remove so that the array will end up in sorted order?

Question

Here is my approach

First I compute the longest non decreasing sub-sequence in $N \log N$ time. Algorithm to do this (that only uses arrays and binary search) can be found here: http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms

Let's suppose the longest subsequence has $L$ elements. Then if $L < N - M$, there isn't any way to solve the problem since there's no subsequence of length $N - M$ that's still sorted.

Otherwise, just remove the $N - L$ elements that aren't in the subsequence, and then remove more at random until exactly M total have been removed. In all this is an $N \log N$ algorithm.

I want to know, is there any more efficient algorithm (i.e. $O( N)$ ) to solve this problem ?

Answer 1

You can adapt the algorithm described in Wikipedia so that it runs in time $O(N\log (N-M))$ if you're only interested in increasing sequences of length at most $N-M$. Judging by the existence of an $N\log N$ lower bound for the general case, $O(N\log(N-M))$ might be optimal. (Your problem is equivalent to the decision problem of whether there exists a non-decreasing subsequence of length $N-M$; this can be reduced to strictly increasing subsequences by adding appropriate $\epsilon$s.)