This is my first attempt at a Code Golf question. If it needs obvious edits, please feel free to make them.
Below is a description of the basic Dropsort algorithm.
Dropsort is run on a list of numbers by examining the numbers in sequence, beginning with the second number in the list. If the number being examined is less than the number before it, drop it from the list. Otherwise, it is in sorted order, so keep it. Then move to the next number.
After a single pass of this algorithm, the list will only contain numbers that are at least as large as the previous number in the list. In other words, the list will be sorted!
For example, given a list of numbers
40,120,122 numbers will be dropped, leaving
1,65,155 in the sorted list.
Let's implement a new sorting algorithm called DropSortTwist.
This sort is identical to Dropsort except that a number (including the first number) that would be kept in Dropsort may optionally be dropped instead. DropSortTwist must return (one of) the longest possible sorted list.
For example, using the same list of numbers as above, DropSortTwist must return either
1,40,120,122. In both cases the
155 number is dropped to achieve a sorted list of length 4, one greater than the Dropsort list.
In this task, you will be given a list of integers as input (STDIN or function argument, you are required to support at least the range of 8-bit signed integers.) You must return the longest possible increasing subsequence.
You may assume that the list is non-empty.
This is code golf, so the shortest program wins.
input output 1 65 40 155 120 122 1 65 120 122 [or] 1 40 120 122 5 1 2 2 3 4 1 2 2 3 4
[1,999]and implements a "must execute this (1000 entry test case) in a 'timely manner'" restriction, making competitive answers unlikely to be transferable in either direction. \$\endgroup\$