# Dropsort with a Twist

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 1,65,40,155,120,122, the 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,65,120,122 or 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.

Test Cases

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

• Welcome to the site! If I understood this correctly you want the Longest increasing subsequence? While the motivations for the challenge are nice it would be best if you could describe the task without relying on users to follow to other links. – Wheat Wizard Aug 9 at 15:29
• @SriotchilismO'Zaic: Thank you! I have tried to clarify the question and reduce the links. – James Aug 9 at 15:40
• Probable dupe, but it is an older question with a different output format (length of subsequence) and some restrictions on time – Jo King Aug 9 at 15:44
• I disagree that this is a dupe. The timing restriction is very significant. I'd expect all serious answers to this question to fail the timing requirements of the older one (my answer sure does). – Grimy Aug 9 at 16:13
• Agreed, I do not think this is a dupe of that dupe target since that one restricts the input domain to [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. – Jonathan Allan Aug 9 at 17:30

# 05AB1E, 8 bytes

æʒD{Q}éθ


Try it online!

æ           # list of subsequences
ʒD{Q}      # filter, keep only the sorted subsequences
é     # sort by length
θ    # get the last (longest) one


# Jelly, 6 bytes

ŒPṢƑƇṪ


Try it online!

### How?

Pretty much the same approach as Grimy's 05AB1E entry

ŒPṢƑƇṪ - Link: list of integers
ŒP     - power-set (all subsequences, from shortest to longest)
Ƈ  - filter keep those which are:
Ƒ   -   invariant when:
Ṣ    -     sorted
Ṫ - tail


# Japt-h, 9 bytes

à ñÊf_eZñ


Try it

# Stax, 9 bytes

éÑ<┬Θ╡Lφ0


Run and debug it

Naive approach: powerset, filter for sorted, sort on length, get tail.

# Ruby, 63 bytes

->a{s=a.size;s-=1until r=a.combination(s).find{|e|e==e.sort};r}


Try it online!

->a{                                    # Anonymous Proc taking array input
s=a.size;                           # Get array size

until                           # Loop until the following condition is non-nil:
r=a.combination(s)        #   Get all subsequences with length s
.find{|e|e==e.sort} #   Find a subsequence that is sorted, else nil
s-=1                                # Reduce s by 1

r                                   # Implicit return the found subsequence
}


# Wolfram Language (Mathematica), 37 bytes

Select[Reverse@Subsets@#,OrderedQ,1]&


Try it online!

The elements of Subsets[ ] are ordered from shortest to longest, so reversing it puts longer subsets first. Then, select the first one which is ordered.

# Python 2, 89 83 bytes

f=lambda A:A>sorted(A)and max([f(A[:i]+A[i+1:])for i in range(len(A))],key=len)or A


Try it online!