Im reading "Introduction to Algorithms: A Creative Approach" and met this question in chapter 1:
Problem 1.3: If you have a list of numbers, delete as few numbers as possible to make the remaining numbers in ascending order.
For example, given an array
9 44 32 12 7 42 34 92
Two options are possible: 9 12 42 92and 32 42 92, and the first has fewer deleted ones.
I tried a recursive algorithm, but did not like its performance, because it still needs to check too many combinations. I found a heuristic algorithm that can get a good result quickly, although I'm not sure if it can guarantee a better result. I searched the Internet, but did not find a discussion on this. I believe that there should be a better algorithm.
I wrote 2 methods here in case you want to check.
UPDATE: I asked solutions on this, @josilber and @templatetypedef gave links and the right direction to view. It turned out that this is a special case of a family of known problems with good solutions. There is no need to write a detailed solution here, the wiki page The largest ever increasing subsequence, sorting patience has provided detailed information.
, , , . - " - ".