Removing Numbers

[mmiguel]

Consider the following list of numbers. Your job is to erase as few of those numbers as possible such that the remaining numbers appear in increasing order.

9 44 32 12 7 42 34 92 35 37 41 8 20 27 83 64 61 28 39 93 29 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

[phil1882]

9 32 34 35 37 41 55 66 72 73 77 83 84

[mmiguel]

9 32 34 35 37 41 55 66 72 73 77 83 84

Nice!

That is a different one than what I had in mind, but it is the same length.

Did you use a general purpose algorithm?

[phil1882]

the idea is this.

start off with the first number; put it in a list.

if the next number is lower than the largest number in the list, drop down a list, or begin a new one.

if the next number is higher, copy the current list, one with that number, one without.

if a lower level list exceeds a higher level one, you can delete the higher level list.