Sottosequenza Crescente più Lunga con Somma Massima
Data una sequenza di
n interi, ti viene chiesto di trovare la sottosequenza crescente più lunga della sequenza. Se esistono più sottosequenze di questo tipo, puoi stamparne una qualsiasi.Una sottosequenza di un array si ottiene eliminando alcuni (eventualmente nessuno) elementi dall’array, senza modificare l’ordine degli elementi rimasti. Ad esempio, se l’array è , allora è una sottosequenza di , mentre non lo è, perché l’ordine degli elementi non viene preservato.
💡
Una sottosequenza crescente di un array è una sottosequenza in cui gli elementi sono in ordine crescente. Ad esempio, se l’array è , allora è una sottosequenza crescente di , mentre non lo è, perché gli elementi non sono in ordine crescente.
Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ 1000), che rappresenta la lunghezza dell’array.La seconda riga contiene
n interi separati da spazio (), che rappresentano gli elementi dell’array.Output
Il programma deve stampare la somma della sottosequenza crescente più lunga con la somma massima.
Ingresso | Uscita |
8
1 3 2 4 5 2 6 5 | 19 |
6
10 9 2 5 3 7 | 14 |
Spiegazione
- Nel primo esempio, la sottosequenza crescente più lunga con somma massima è .
- Nel secondo esempio, la sottosequenza crescente più lunga con somma massima è .
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB