Codegolf — Разбиение На Возрастающие Подпоследовательности

Спецификация

Эту задачу легко сформулировать: ваши входные данные представляют собой непустой массив неотрицательных целых чисел, и ваша задача — разбить его на как можно меньшее количество возрастающих подпоследовательностей.

 
 [0] -> [[0]]
[3,5,8] -> [[3,5,8]]
[2,2,2,2] -> [[2,2,2,2]]
[1154,1012,976,845] -> [[845],[976],[1012],[1154]]
[6,32,1,2,34,8] -> [[1,2,8],[6,32,34]]
[1,12,1,12,1,13] -> [[1,1,1,13],[12,12]]
[6,4,6,13,18,0,3] -> [[0,3],[4,6,13,18],[6]]
[1,2,3,2,3,4,7,1] -> [[1,1],[2,2,3,4,7],[3]]
[0,9,2,7,4,5,6,3,8] -> [[0,2,3,8],[4,5,6],[7],[9]]
[7,1,17,15,17,2,15,1,6] -> [[1,1,6],[2,15],[7,15,17],[17]]
[4,12,2,10,15,2,2,19,16,12] -> [[2,2,2,12],[4,10,15,16],[12,19]]
[10,13,9,2,11,1,10,17,19,1] -> [[1,1],[2,10,17,19],[9,11],[10,13]]
[3,7,3,8,14,16,19,15,16,2] -> [[2],[3,3,8,14,15,16],[7,16,19]]
[15,5,13,13,15,9,4,2,2,17] -> [[2,2,17],[4],[5,9],[13,13,15],[15]]
 
 

• такой, что: A form a partition of B Каждый массив в A 1 2 1 2 5 4 7 1 B[0] 1 B[1] 1 2 4 7 B[2] 1 2 5 is the singleton array containing B = [[1],[1,2,4,7],[1,2,5]] на непересекающиеся (не обязательно смежные) подпоследовательности. Индуктивно это означает, что либо A = [1,2,1,2,5,4,7,1] is a subsequence of B , или первый элемент B with that subsequence removed.
• а остальные образуют раздел A is (not necessarily strictly) increasing.
• Каждый массив в A is minimal.

Количество массивов в

И ввод, и вывод могут быть приняты в собственном формате массива вашего языка.

Обратите внимание, что правильных результатов может быть несколько. B . One possible output is A Пример

Рассмотрим входной массив A is increasing. Finally, B . B is also minimal. Thus it's a valid output.

Условие разделения видно из этой диаграммы:

Кроме того, каждый массив в

нельзя разбить на две возрастающие подпоследовательности, поэтому длина

Правила и подсчет очков

Вы можете написать функцию или полную программу.

Хаскель, 54 байта

 
 
 fTu&ahfSI+THGHGQm[)Q   implicit: Q = input list

m[)Q   create a list of empty lists and assign to G

u            Q       iterate over all numbers H in input:

f     G             filter for lists T in G, which satisfy:

+TH                 create a new list out of T and H

SI                    and check if it is sorted

h                    take the first such list T

a        H            and append H

&          G           logical and with G (so that u doesn't overwrite G)
fT                     remove all empty lists
 
 
 

Пример использования: input -> len(input)

Как это работает: просмотрите список ввода, начиная с правого конца. Создайте выходной список (списков), добавив текущий элемент fTu&ahfSI+THGHGQm[)Q to first sublist n где l is less or equal to the head of n . Если его нет, создайте новый одноэлементный список l at the end of the output list.

Пиф, 20 байт

Попробуйте онлайн: Демонстрация или Тестовый набор

Жадный подход. я создаю [[2,2,2,12],[4,10,15,16],[12,19]] empty lists. Then I iterate over each number in the foldr(#)[] [4,12,2,10,15,2,2,19,16,12] и выберите первый список, который все еще отсортирован после добавления номера.

Объяснение: