Given an array of N integers, how can you find M elements to remove so that the array will end up in sorted order?
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.)