An algorithm to remove the least amount of numbers in the list in increasing and decreasing order?

Question

Consider the following numbers:

9,44,32,12,7,45,31,98,35,37,41,8,20,27,83,64,61,28,39,93,29,92,17,13,14,55,21,66,72,23,73,99,1,2,88,77,3,65,83,84,62,5,11,74,68,76,78,67,75,69,70,22,71,24,25,26.

I try to implement an algorithm to remove the least amount of numbers in the list to make the sequence

a) increasing order b) decreasing order

I already tried with the shortest and longest subsecuence. Dont want the code, only the explanation or a pseudo code,i can't understand how to solve the problem thanks!

Answer 1

Since it has already been mentioned, I will add my 2 cents. Most probably this will be asked in interview in those circumstances, the running time(efficiency) is a major concern. So the same problem can be tackled with many algorithms depending on the time they take to execute. The best known algorithm is of order O(nlogn). Other important one can like Dynamic programming paradigm can also be applied to yield a solution of O(n^2).

O(n^2) here

O(nlogn) here

Answer 2

This is a lightly camouflaged Longest increasing (decreasing) subsequence problem. The algorithm to solving your problem is as follows:

• Find the longest increasing (decreasing) subsequence in the array
• Remove all elements that do not belong to the longest increasing subsequence.

Since the increasing/decreasing subsequence is longest, the amount of numbers that you will remove is the smallest.

Wikipedia article has a nice pseudocode for solving the LIS/LDS problem. You can substitute binary search for a linear one unless the original sequence is 1000+ elements long.