Finde die längste aufsteigende Teilfolge
Gegeben ist ein Array aus
n ganzen Zahlen. Deine Aufgabe besteht darin, die längste aufsteigende Teilfolge des Arrays zu finden. Wenn es mehrere solche Teilfolgen gibt, kannst du beliebig eine davon ausgeben.Eine Teilfolge eines Arrays erhältst du, indem du einige (möglicherweise auch keine) Elemente aus dem Array entfernst, ohne die Reihenfolge der übrigen Elemente zu verändern. Zum Beispiel ist, wenn das Array lautet, eine Teilfolge von . Dagegen ist keine Teilfolge von , weil die ursprüngliche Reihenfolge nicht beibehalten wird.
💡
Eine aufsteigende Teilfolge eines Arrays ist eine Teilfolge, in der die Elemente in einer streng ansteigenden Reihenfolge erscheinen. Wenn beispielsweise ist, dann ist eine aufsteigende Teilfolge von . Dagegen ist keine aufsteigende Teilfolge, da die Elemente darin nicht in aufsteigender Reihenfolge liegen.
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 100 000), die die Länge des Arrays angibt.Die zweite Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (), welche die Elemente des Arrays darstellen.Ausgabe
Die erste Zeile soll eine ganze Zahl
k enthalten – die Länge der längsten aufsteigenden Teilfolge im Array.Die zweite Zeile soll
k durch Leerzeichen getrennte ganze Zahlen enthalten, die die längste Teilfolge selbst repräsentieren. Gibt es mehrere mögliche Lösungen, kannst du eine beliebige davon ausgeben.Beispiele
Eingabe | Ausgabe |
8
1 3 2 4 5 2 6 5 | 5
1 2 4 5 6 |
6
10 9 2 5 3 7 | 3
2 5 7 |
Hinweis
Im zweiten Beispiel ist die Teilfolge ebenfalls eine gültige aufsteigende Teilfolge der Länge 3.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB