Спецификация
Эта задача проста в утверждении: ваш ввод представляет собой непустой массив неотрицательных целых чисел, и ваша задача состоит в том, чтобы разбить его на как можно меньшее число увеличивающихся подпоследовательностей. Более формально, если входной массив есть A
, то выходной это массив массивов, B
такой что:
- Каждый массив
B
образует разбиениеA
на непересекающиеся (не обязательно смежные) подпоследовательности. Индуктивно это означает, что либоB
массив синглтона содержитA
, либо первый элементB
является подпоследовательностью,A
а остальные образуют разделA
с удаленной этой подпоследовательностью. - Каждый массив в
B
(не обязательно строго) увеличивается. - Количество массивов в
B
минимально.
И ввод, и вывод могут быть приняты в собственном формате массива вашего языка. Обратите внимание, что может быть несколько правильных выходов.
пример
Рассмотрим входной массив A = [1,2,1,2,5,4,7,1]
. Одним из возможных выходных данных является B = [[1],[1,2,4,7],[1,2,5]]
. Состояние раздела видно из этой диаграммы:
A 1 2 1 2 5 4 7 1
B[0] 1
B[1] 1 2 4 7
B[2] 1 2 5
Кроме того, каждый массив в B
увеличивается. Наконец, A
нельзя разбить на две возрастающие подпоследовательности, поэтому длина B
также минимальна. Таким образом, это действительный вывод.
Правила и оценки
Вы можете написать функцию или полную программу. Побеждает меньшее количество байтов, и стандартные лазейки запрещены. Срок не ограничен, но вы должны избегать решения во всех тестовых случаях перед его отправкой.
Контрольные примеры
Отображается только один возможный вывод, но может быть несколько допустимых параметров. В частности, порядок массивов в результате не имеет значения (но каждый отдельный массив должен быть в порядке возрастания).
[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]]
[0,5,2,0] -> [[0,5],[0,2]]
(т. Е. Рециркулируют первый ноль вместо того, чтобы использовать каждый из них один раз). Это намеренно?B
, надеюсь, теперь они понятнее.Ответы:
Haskell, 54 байта
Пример использования:
foldr(#)[] [4,12,2,10,15,2,2,19,16,12]
->[[2,2,2,12],[4,10,15,16],[12,19]]
Как это работает: просмотрите список ввода, начиная с правого конца. Создайте выходной список (списков), добавив текущий элемент
n
к первому подсписку,l
гдеn
он меньше или равен заголовкуl
. Если их нет, создайте новый одноэлементный списокn
в конце списка вывода.источник
Pyth, 20 байтов
Попробуйте онлайн: демонстрация или тестовый набор
Жадный подход. Я создаю
len(input)
пустые списки. Затем я перебираю каждое число вinput
списке «Выбрать первый», который все еще сортируется после добавления номера.Объяснение:
источник