spécification

Ce défi est simple à énoncer: votre entrée est un tableau non vide d'entiers non négatifs, et votre tâche consiste à le partitionner en aussi peu de sous-séquences croissantes que possible. Plus formellement, si le tableau d'entrée est A, alors la sortie est un tableau de tableaux Btel que:

• Chaque tableau Bforme une partition de Asous-séquences disjointes (pas nécessairement contiguës). Inductivement, cela signifie que soit Ble tableau singleton contient A, soit le premier élément de Best une sous-séquence de Aet le reste forme une partition de Acette sous-séquence supprimée.
• Chaque tableau en Baugmente (pas nécessairement strictement).
• Le nombre de tableaux dans Best minimal.

L'entrée et la sortie peuvent être prises dans le format de tableau natif de votre langue. Notez qu'il peut y avoir plusieurs sorties correctes.

Exemple

Considérez le tableau d'entrée A = [1,2,1,2,5,4,7,1]. Une sortie possible est B = [[1],[1,2,4,7],[1,2,5]]. La condition de partition est évidente à partir de ce diagramme:

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

De plus, chaque tableau en Baugmente. Enfin, Ane peut pas être divisé en deux sous-séquences croissantes, donc la longueur de Best également minimale. C'est donc une sortie valide.

Règles et notation

Vous pouvez écrire une fonction ou un programme complet. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites. Il n'y a pas de limite de temps, mais vous devez évaluer votre solution sur tous les cas de test avant de la soumettre.

Cas de test

Une seule sortie possible est affichée, mais il peut y avoir plusieurs options valides. En particulier, l'ordre des tableaux dans le résultat n'a pas d'importance (mais chaque tableau individuel doit être en ordre croissant).

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

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

Exemple d'utilisation: foldr(#)[] [4,12,2,10,15,2,2,19,16,12]->[[2,2,2,12],[4,10,15,16],[12,19]]

Comment ça marche: parcourez la liste de saisie en commençant à l'extrémité droite. Construisez la liste de sortie (des listes) en ajoutant l'élément courant nà la première sous-liste loù nest inférieur ou égal à la tête de l. S'il n'y en a pas, créez une nouvelle liste singleton nà la fin de la liste de sortie.

Pyth, 20 octets

fTu&ahfSI+THGHGQm[)Q

Essayez-le en ligne: démonstration ou suite de tests

Approche gourmande. Je crée len(input)des listes vides. Ensuite, j'itère sur chaque numéro de la inputliste et choisissez la première, qui est toujours triée après avoir ajouté le numéro.

Explication:

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