Längste aufsteigende Teilfolge mit maximaler Summe
Gegeben ist ein Array mit
n ganzen Zahlen. Gesucht wird die längste aufsteigende Teilfolge des Arrays. Falls es mehrere solcher Teilfolgen gibt, kann jede beliebige ausgegeben werden.Eine Teilfolge eines Arrays erhält man, indem man einige (möglicherweise auch keine) Elemente aus dem Array entfernt, ohne die Reihenfolge der verbleibenden Elemente zu verändern. Zum Beispiel, wenn das Array ist, dann ist eine Teilfolge von , aber nicht, da hier die ursprüngliche Reihenfolge der Elemente nicht beibehalten wird.
💡
Eine aufsteigende Teilfolge eines Arrays ist eine Teilfolge, in der die Elemente in aufsteigender Reihenfolge angeordnet sind. Wenn zum Beispiel das Array ist, dann ist eine aufsteigende Teilfolge von , aber nicht, da die Elemente nicht aufsteigend sind.
Eingabe
Die erste Zeile der Eingabe enthält eine 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 Summe der längsten aufsteigenden Teilfolge mit der maximalen Summe ausgeben.
Eingabe | Ausgabe |
8
1 3 2 4 5 2 6 5 | 19 |
6
10 9 2 5 3 7 | 14 |
Erklärung
- Im ersten Beispiel ist die längste aufsteigende Teilfolge mit maximaler Summe .
- Im zweiten Beispiel ist die längste aufsteigende Teilfolge mit maximaler Summe .
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB