Especificación

Este desafío es fácil de establecer: su entrada es una matriz no vacía de enteros no negativos, y su tarea es dividirla en la menor cantidad de subsecuencias crecientes posible. Más formalmente, si la matriz de entrada es A, entonces la salida es una matriz de matrices Btales que:

• Cada matriz Bforma una partición Aen subsecuencias disjuntas (no necesariamente contiguas). Inductivamente, esto significa que o bien Bla matriz singleton contiene A, o el primer elemento de Bes una subsecuencia de Ay el resto forma una partición de Acon esa subsecuencia eliminada.
• Cada matriz Bestá aumentando (no necesariamente estrictamente).
• El número de matrices en Bes mínimo.

Tanto la entrada como la salida se pueden tomar en el formato de matriz nativo de su idioma. Tenga en cuenta que puede haber varias salidas correctas.

Ejemplo

Considere la matriz de entrada A = [1,2,1,2,5,4,7,1]. Una salida posible es B = [[1],[1,2,4,7],[1,2,5]]. La condición de partición es evidente a partir de este diagrama:

A    1 2 1 2 5 4 7 1
B[0]               1
B[1] 1 2       4 7
B[2]     1 2 5

Además, cada matriz Bestá aumentando. Finalmente, Ano se puede dividir en dos subsecuencias crecientes, por lo que la longitud de Bes también mínima. Por lo tanto, es una salida válida.

Reglas y puntaje

Puede escribir una función o un programa completo. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten. No hay límite de tiempo, pero debe evaluar su solución en todos los casos de prueba antes de enviarla.

Casos de prueba

Solo se muestra una salida posible, pero puede haber varias opciones válidas. En particular, el orden de las matrices en el resultado no importa (pero cada matriz individual debe estar en orden creciente).

[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]]

Haskell, 54 bytes

n#[]=[[n]]
n#(l:c)|[n]<=l=(n:l):c|1<2=l:n#c
foldr(#)[]

Ejemplo de uso: foldr(#)[] [4,12,2,10,15,2,2,19,16,12]->[[2,2,2,12],[4,10,15,16],[12,19]]

Cómo funciona: revise la lista de entrada que comienza en el extremo derecho. Cree la lista de salida (de listas) anteponiendo el elemento actual na la primera sublista ldonde nsea ​​menor o igual a la cabeza de l. Si no hay ninguno, haga una nueva lista de singleton nal final de la lista de salida.

Pyth, 20 bytes

fTu&ahfSI+THGHGQm[)Q

Pruébelo en línea: Demostración o conjunto de pruebas

Enfoque codicioso. Yo creo len(input)listas vacías. Luego itero sobre cada número y inputelijo la primera lista, que aún se ordena después de agregar el número.

Explicación:

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