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