Längste aufsteigende Teilfolge 2
Angenommen, wir haben ein Array mit
n ganzen Zahlen. Wir sollen die längste aufsteigende Teilfolge dieses Arrays finden. Falls es mehrere solche Teilfolgen gibt, darf jede beliebige davon ausgegeben werden.Eine Teilfolge eines Arrays erhält man, indem man einige (möglicherweise keine) Elemente des Arrays entfernt, ohne die Reihenfolge der verbleibenden Elemente zu verändern. Zum Beispiel ist bei dem Array die Folge eine Teilfolge von . Hingegen ist keine Teilfolge von , da dort die ursprüngliche Reihenfolge nicht beibehalten wird.
💡
Eine aufsteigende Teilfolge eines Arrays ist eine Teilfolge, in der die Elemente in aufsteigender Reihenfolge angeordnet sind. Zum Beispiel ist bei dem Array die Folge eine aufsteigende Teilfolge von , während aufgrund der nicht durchgängig steigenden Elemente keine aufsteigende Teilfolge ist.
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
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