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.

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.

Erklärung

1. Im ersten Beispiel ist die längste aufsteigende Teilfolge mit maximaler Summe .

2. Im zweiten Beispiel ist die längste aufsteigende Teilfolge mit maximaler Summe .