Trova la più lunga sottosequenza crescente
Dato un array di
n interi, devi trovare la più lunga sottosequenza crescente dell'array. Se ne esistono diverse con la stessa lunghezza, puoi restituirne una a tua scelta.Una sottosequenza di un array si ottiene rimuovendo alcuni (eventualmente nessuno) elementi dall'array, senza alterare l'ordine di quelli rimanenti. Ad esempio, se l'array è , allora è una sottosequenza di , mentre non lo è, perché l’ordine degli elementi non è rispettato.
💡
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), che rappresenta la lunghezza dell'array.La seconda riga contiene
n numeri interi separati da spazi (), ovvero gli elementi dell'array.Output
La prima riga deve contenere un intero
k, che è la lunghezza della più lunga sottosequenza crescente dell'array.La seconda riga deve contenere
k interi separati da spazi, corrispondenti alla sottosequenza stessa. In caso di più soluzioni valide, puoi restituirne una qualsiasi.Examples
Input | Output |
8
1 3 2 4 5 2 6 5 | 5
1 2 4 5 6 |
6
10 9 2 5 3 7 | 3
2 5 7 |
Note
Nel secondo esempio, la sottosequenza è un’altra valida sottosequenza crescente di lunghezza 3.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB