Specyfikacja

Wyzwanie to jest łatwe do stwierdzenia: dane wejściowe to niepusta tablica nieujemnych liczb całkowitych, a Twoim zadaniem jest podzielenie ich na jak najmniej rosnących podsekwencji. Bardziej formalnie, jeśli tablica wejściowa jest A, to dane wyjściowe to tablica tablic Btakich, że:

• Każda tablica Btworzy podział Ana rozłączne (niekoniecznie ciągłe) podsekwencje. Indukcyjnie oznacza to, że albo Bzawiera tablicę singletonów A, albo pierwszy element Bjest podsekwencją, Aa reszta tworzy partycję Az usuniętą podsekwencją.
• Każda tablica Brośnie (niekoniecznie ściśle).
• Liczba tablic Bjest minimalna.

Zarówno dane wejściowe, jak i wyjściowe mogą być pobierane w rodzimym formacie tablicowym Twojego języka. Pamiętaj, że może istnieć kilka poprawnych wyników.

Przykład

Rozważ tablicę wejściową A = [1,2,1,2,5,4,7,1]. Jednym z możliwych wyników jest B = [[1],[1,2,4,7],[1,2,5]]. Warunki partycji są widoczne na tym schemacie:

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

Z każdą kolejną tablicą Brośnie. Wreszcie, Anie można podzielić na dwa rosnące podsekwencje, więc długość Bjest również minimalna. Dlatego jest to poprawny wynik.

Zasady i punktacja

Możesz napisać funkcję lub pełny program. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone. Nie ma ograniczenia czasowego, ale powinieneś ewakuować swoje rozwiązanie na wszystkich testowych przypadkach przed jego przesłaniem.

Przypadki testowe

Wyświetlane jest tylko jedno możliwe wyjście, ale może istnieć kilka prawidłowych opcji. W szczególności kolejność tablic w wyniku nie ma znaczenia (ale każda pojedyncza tablica powinna być w kolejności rosnącej).

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

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

Przykład użycia: foldr(#)[] [4,12,2,10,15,2,2,19,16,12]->[[2,2,2,12],[4,10,15,16],[12,19]]

Jak to działa: przejrzyj listę danych wejściowych, zaczynając od prawego końca. Zbuduj listę wyjściową (list), przygotowując bieżący element ndo pierwszej podlisty, lgdzie njest mniejsza lub równa główce l. Jeśli nie ma, utwórz nową listę singletonów nna końcu listy wyników.

Pyth, 20 bajtów

fTu&ahfSI+THGHGQm[)Q

Wypróbuj online: pakiet demonstracyjny lub testowy

Chciwe podejście. Tworzę len(input)puste listy. Następnie iteruję każdą liczbę na liście inputwyboru pierwszej, która nadal jest sortowana po dodaniu liczby.

Wyjaśnienie:

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