Longest Increasing Subsequence 2
Dato un array di
n interi, devi trovare la sottosequenza crescente più lunga dell’array. Se esistono più sottosequenze di lunghezza massima, puoi restituirne una qualsiasi.Una sottosequenza di un array si ottiene eliminando alcuni (anche nessuno) elementi dell’array, senza alterare l’ordine di quelli che rimangono. Ad esempio, se l’array è , allora è una sottosequenza di , ma 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 ≤ 100 000), 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 lunghezza della sottosequenza crescente più lunga dell’array.
Esempi
Ingresso | Uscita |
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