Sottosequenza Crescente Più Lunga 1
Dato un array di
n interi, ti viene richiesto di trovare la sottosequenza crescente più lunga dell’array. Nel caso in cui ne esistano più di una, puoi restituirne una qualsiasi.Una sottosequenza di un array si ottiene eliminando alcuni (eventualmente zero) elementi dall’array, senza modificare l’ordine di quelli rimanenti. Ad esempio, se l'array è , allora è una sottosequenza di , mentre non è una sottosequenza di , poiché non viene preservato l’ordine degli elementi.
💡
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 è una sottosequenza crescente di , dato che gli elementi non sono in ordine crescente.
Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ 1000), la lunghezza dell’array.La seconda riga contiene
n interi separati da uno spazio (), che rappresentano gli elementi dell’array.Output
Il programma deve stampare la lunghezza della sottosequenza crescente più lunga dell’array.
Esempi
Input | Output |
8
1 3 2 4 5 2 6 5 | 5 |
6
10 9 2 5 3 7 | 3 |
Spiegazione
- Nel primo esempio, la sottosequenza crescente più lunga dell’array è .
- Nel secondo esempio, la sottosequenza crescente più lunga dell’array è .
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB