Dropsort with a Twist

Question

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

Answer 1

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

Answer 2

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

Answer 3

Japt -h, 9 bytes

à ñÊf_eZñ

Try it

Answer 4

Stax, 9 bytes

éÑ<┬Θ╡Lφ0

Run and debug it

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

Answer 5

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
}

Answer 6

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.

Answer 7

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!