Longueur maximale d'un sous-tableau commun
Étant donné deux tableaux d'entiers
a et b, vous devez déterminer la longueur maximale d'un sous-tableau qui apparaît à la fois dans a et b.Entrée
La première ligne de l'entrée contient un entier
n (1 ≤ n ≤ 1000).La deuxième ligne contient
n entiers séparés par des espaces (0 ≤ ≤ 100).La troisième ligne contient
n entiers séparés par des espaces (0 ≤ ≤ 100).Sortie
Le programme doit afficher la longueur maximale du sous-tableau commun.
Exemples
Entrée | Sortie |
4
1 2 4 2
0 4 2 1 | 2 |
3
5 5 5
5 5 5 | 3 |
Explication
- Le plus long sous-tableau commun est
4 2, présent dans les deux tableaux ⇒ longueur 2.
- Les deux tableaux sont identiques ⇒ le plus long sous-tableau commun est le tableau complet ⇒ longueur 3.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB