Алгоритм сортировки

33

Существует «алгоритм сортировки», иногда называемый сортировкой Сталина, в котором для сортировки списка вы просто удаляете элементы из списка, пока он не будет отсортирован в порядке возрастания. Например список

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

При "сортировке" по сталину сортировка становится

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

Три были удалены, потому что это было не в порядке.

Теперь очевидно, что есть много способов удалить элементы для сортировки списка. Например, любой список, содержащий менее двух элементов, должен быть отсортирован, поэтому, просто удалив достаточное количество элементов вслепую, мы всегда можем отсортировать список. Поскольку это так, мы заботимся только о самом длинном из результатов сталинского рода.

Ваша задача состоит в том, чтобы взять список натуральных чисел и вывести длину самого длинного отсортированного (возрастающего) списка, который можно получить, удалив элементы из исходного списка. То есть найдите длину самого длинного отсортированного (возможно, несмежного) подсписка.

Сортированные списки могут содержать один и тот же элемент более одного раза подряд. Вам не нужно поддерживать пустой список, если ваша программа не пуста.

счет

Ваш ответ будет оцениваться по длине самого длинного из возможных сталинских сортов. Программы будут интерпретироваться как последовательность байтов, а не символов, и их порядок будет естественным, который возникает при интерпретации байтов как чисел. Чем ниже баллы, тем лучше.

Это не

Вот отличный инструмент, который поможет вам оценить ваши ответы.

Контрольные примеры

[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
Мастер пшеницы
источник
3
Вкратце: выведите длину самой длинной (не строго) возрастающей последовательности .
user202729
1
Мне нравится правило «Вам не нужно поддерживать пустой список, если ваша программа не пуста».
Paŭlo Ebermann
Это испытание очень напоминает мне дропсорт: codegolf.stackexchange.com/questions/61808/…
Stefnotch
1
Я сделал проверку в ptpb.pw/SVSt.html . Все еще не очень функционально, но это работает. (TODO: * гистограмма * разбиение на наименее убывающие последовательности * поддержка других кодовых страниц)
user202729
@ user202729 Круто! Я добавил это к посту. Не стесняйтесь редактировать новые версии в случае необходимости.
Wheat Wizard

Ответы:

8

Python 2 , длина 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))

Выход через код выхода.

Попробуйте онлайн!

Как это работает

Во всех случаях массив L отслеживает самые длинные отсортированные подмассивы, встречающиеся до сих пор; L[a-1] - длина самого длинного, который заканчивается на a .

Первоначально мы не обрабатывали элементы массива, поэтому L полностью состоит из нулей.

a[L[0],...,L[a-1]]aaaL[a-1]

L

Деннис
источник
Не могли бы вы объяснить, почему это работает? У меня трудные времена, чтобы понять это :(
Мертвый Опоссум
Я добавил объяснение.
Деннис
4

Желе , длина  4  2

ṢƑƇZLƲ}ŒP

Попробуйте онлайн!

Байт в кодовой странице желе

183 146 144 90 76 169 125 19 80

Как это работает

ṢƑƇ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.
Деннис
источник
3

Pyth, оценка 3 2 ( 7 байт)

leSI#y

Спасли очко благодаря Андерсу Касерегу.
Попробуй здесь

объяснение

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.

источник
leSI#y2 балла
Андерс Касеорг
2

R , Оценка 15 11, 72 62 байта

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

Попробуйте онлайн!

Порты Денниса Python ответ Р.

Giuseppe
источник
Простое изменение имен переменных не поможет, потому что, как показывает ваша последняя ссылка, ни одна из них не используется в (найденной) подстроке, которая дает оценку 15.
Орджан Йохансен,
@ ØrjanJohansen ну, конечно, я довольно тупой. Я полагаю, нужен другой подход.
Джузеппе
2

Брахилог , длина 2 (4 байта)

⊇≤₁l

Попробуйте онлайн!

Ответ, который компенсирует то, что он не такой уж и короткий.

( 08 03 80 6Cв кодовой странице брахилога)

        Output
   l    the length of
 ≤₁     a non-decreasing
⊇       sublist of
        the input.
        (maximizing the size of the sublist)
Несвязанная строка
источник
Я придумал ►LSnmOṖдля Husk, но его оценка (по крайней мере для его длины) слишком плоха, чтобы беспокоиться о публикации ...
Несвязанная строка