最大共通部分配列の長さ
整数配列 a
と b
が与えられたとき、両方の配列に共通して現れる部分配列の中で、最も長いものの長さを求めます。
入力
最初の行には、整数 n
(1 ≤ n ≤ 1000) が1つ与えられます。
2行目には、n
個の整数 (0 ≤ ≤ 100) がスペース区切りで与えられます。
3行目には、n
個の整数 (0 ≤ ≤ 100) がスペース区切りで与えられます。
出力
共通部分配列の最大長を出力してください。
例
入力 | 出力 |
---|---|
4 | 2 |
3 | 3 |
解説
与えられた2つの配列に共通して含まれる最も長い部分配列は
4 2
で、その長さは2です。2つの配列が同一のため、最も長い部分配列は配列全体となり、長さは3です。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB