Längste aufsteigende Teilfolge 1
Gegeben ist ein Array aus
n Ganzzahlen. Ihre Aufgabe ist es, die längste aufsteigende Teilfolge dieses Arrays zu finden. Falls es mehrere Lösungen gibt, können Sie eine beliebige davon ausgeben.Eine Teilfolge eines Arrays entsteht, indem man einige (möglicherweise keine) Elemente entfernt, ohne die Reihenfolge der verbleibenden Elemente zu verändern. Wenn zum Beispiel das Array gegeben ist, dann ist eine Teilfolge von . Dagegen ist keine Teilfolge von , da die Reihenfolge der Elemente nicht beibehalten wurde.
💡
Eine ansteigende Teilfolge eines Arrays ist eine Teilfolge, in der die Elemente in aufsteigender Reihenfolge stehen. Zum Beispiel ist bei die Teilfolge ansteigend. Dagegen ist keine ansteigende Teilfolge von , da die Elemente nicht in aufsteigender Reihenfolge angeordnet sind.
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 1000), 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
Das Programm soll die Länge der längsten aufsteigenden Teilfolge des Arrays ausgeben.
Beispiele
Eingabe | Ausgabe |
8
1 3 2 4 5 2 6 5 | 5 |
6
10 9 2 5 3 7 | 3 |
Erklärung
- Im ersten Beispiel ist die längste aufsteigende Teilfolge des Arrays .
- Im zweiten Beispiel ist die längste aufsteigende Teilfolge des Arrays .
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB