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

Assumption :  Final sorted order is increasing order Step 1 : Find the longest increasing sequence in the given set of elements. This can be done in O(n^2) time. Suppose the number of elements are not present in the longest increasing sequence are 'k' . Now k <= m otherwise we could not get a sorted order by removing m elements because at least those elements that are not in the sequence needs to be removed . Step 2 : Remove any of the (m-k) elements from the longest increasing sequence to get a total of m elements removed. Now what we have is a sorted order of (n-m) elements. The complexity of algorithm is O(n^2)  as step 1 takes O(n^2) time and step 2 takes O(m-k) time. If the final sorted order is needed as decreasing order, find the longest decreasing sequence in Step 1 instead of increasing sequence.

This answer describes solution in O(N log N) time complexity. You know that you have array with N elements and after removing M elements there are N-M elements left in sorted order. So what is left is non-decreasing subsequence of length K, K=N-M. We can find such subsequence in time O(NlogN). Let's use dynamic programming here. Let d[i] be the least number that can be in the end of non-decreasing subsequence of length I. Base of dynamics: d[0] = -infinity. Rest of d is +infinity. Let's iterate through all N elements and for.every a[i] we will try to update array d. Simple code: For x in a For j in 0..k-1 If x >= d[i] and x < d[i+1] d[i+1] = x break It works in O(N*N) and now we will optimize it to O(NlogN). You can notice that with such algorithm d[i-1] is always less then or equal to d[i]. Another key moment is that every a[i] updates only one d[j] at max. (it is easy to prove, once you update one length there is no way it can update any further). These gives us a pretty much good place for binary search optimization. I mean, practically for every x = a[i], you need to find right most position j in d, so x is equal or greater than d[j] and d[j+1] is less then x. Set binary search and now you have the least number standing last in subsequence of length k for every k in 1..K. How to recover the answer? There is a common practice in dynamic programming, whenever you update some value, remember, what index updated this value and then it will be easy to recover the answer sequence from the end. Same time complexity can be reached using different approach with data structure called segment tree.

Although finding the [math]M[/math] elements takes [math]O(N \log N)[/math] time, there’s a nice approximation algorithm to find at most [math]2M[/math] elements such that the rest are in sorted order, in [math]O(N)[/math] time—see .