Istnieje „algorytm sortowania”, zwany czasem sortowaniem Stalina, w którym w celu posortowania listy wystarczy usunąć elementy z listy, aż zostanie ona posortowana w porządku rosnącym. Na przykład lista

[1, 2, 4, 5, 3, 6, 6]

Kiedy „posortowane” za pomocą Stalina staje się sortowanie

[1, 2, 4, 5, 6, 6]

Trójka została usunięta, ponieważ była niesprawna.

Oczywiście istnieje wiele sposobów usuwania elementów w celu posortowania listy. Na przykład każda lista zawierająca mniej niż dwa elementy musi zostać posortowana, więc wystarczy usunąć ślepo wystarczającą liczbę elementów, abyśmy zawsze mogli sortować listę. Ponieważ tak jest, zależy nam tylko na jak najdłuższym wyniku ze stali Stalina.

Twoim zadaniem będzie pobranie listy dodatnich liczb całkowitych i wyprowadzenie długości najdłuższej posortowanej (rosnącej) listy, którą można uzyskać, usuwając elementy z oryginalnej listy. To jest długość najdłuższej posortowanej (być może nieciągłej) podlisty.

Posortowane listy mogą mieć ten sam element więcej niż raz z rzędu. Nie musisz obsługiwać pustej listy, chyba że sam program jest pusty.

Punktacja

Twoja odpowiedź będzie oceniana według długości najdłuższego możliwego rodzaju Stalina. Programy będą interpretowane raczej jako ciąg bajtów niż znaków, a ich kolejność będzie naturalna, która powstaje w wyniku interpretacji bajtów jako liczb. Niższe wyniki są lepsze.

To nie jest golf golfowy

Oto fajne narzędzie, które pomoże Ci zdobyć odpowiedzi.

Przypadki testowe

[1, 2, 4, 5, 3, 6, 6] -> 6
[19, 2] -> 1
[3, 3, 4, 3] -> 3
[10] -> 1
[1, 2, 4, 9] -> 4
[1, 90, 2, 3, 4, 5] -> 5
[1, 90, 91, 2, 3, 4, 5] -> 5

Python 2 , długość 14 12 10 9

M=max;X=exit;i=input();L=[0]*M(i)
for	a	in	i:L[a-1]=M(L[:a])+1
X(M(L))

Wyjście odbywa się za pomocą kodu wyjścia.

Wypróbuj online!

Jak to działa

$L$$L[a-1]$$a$

$L$

$a$$[L[0], \dots, L[a-1]]$$a$$a$$a$$L[a-1]$

$L$

Język Wolfram (Mathematica) , wynik 9

Length@*LongestOrderedSequence

Wypróbuj online!

Perl 6 , wynik 9

*.combinations.map({@^a*[<=] @a}).max

Wypróbuj online!

Haskell , wynik 8 7, 48 bajtów

(l:k)%d|d>l=k%d|3>2=max(1+k%l)(k%d)
c%b=0
a=(%0)

Wypróbuj online!

Najdłuższa posortowana lista jest

%%%%%%)

Galaretka , długość  4  2

ṢƑƇZLƲ}ŒP

Wypróbuj online!

Bajty na stronie kodowej Jelly

183 146 144 90 76 169 125 19 80

Jak to działa

ṢƑƇZLƲ}ŒP  Main link. Argument: A (array)

       ŒP  Powerset; yield P, the array of all sub-arrays of A.
     Ʋ     Vier; combine the preceding four links into a monadic chain...
      }    and apply the chain to the right argument (P).
  Ƈ            Comb; only keep arrays for which the link to the left returns 1.
ṢƑ             Sort fixed; yield 1 if sorting doesn't alter the array.
   Z           Zip; read the filtered powerset by columns.
    L          Take the length.

Pyth, wynik 3 2 ( 7 bajtów)

leSI#y

Zaoszczędź punkt dzięki Andersowi Kaseorgowi.
Wypróbuj tutaj

Wyjaśnienie

leSI#y
     yQ    Take the power set of the (implicit) input (preserving order).
  SI#      Get the ones that are sorted.
 e         Take the last (longest).
l          Get the length.

Stax , 4 maksymalna długość sortowania według Stalina

S{:^fF%|M

Uruchom i debuguj

Działa to w ten sposób.

S       powerset of input
{:^f    filter by non-descending sequences
F%|M    take the maximum length remaining

R , wynik 15 11, 72 62 bajtów

function(L,M=max,A=1:M(L)*0){for(Y in L)A[Y]=M(A[1:Y])+1;M(A)}

Wypróbuj online!

Odpowiedź Pytona Dennisa na port R.

Brachylog , długość 2 (4 bajty)

⊇≤₁l

Wypróbuj online!

Odpowiedź, która rekompensuje to, że jest tak zwięzła, ponieważ nie jest o wiele krótsza.

( 08 03 80 6Cna stronie kodowej Brachylog)

        Output
   l    the length of
 ≤₁     a non-decreasing
⊇       sublist of
        the input.
        (maximizing the size of the sublist)