Maximum Length of Common Subarray
Given two integer arrays
a
and b
, you are asked to find the maximum length of the subarray that appears in both a
and b
. Input
The first line of the input contains a single integer
n
(1 ≤ n ≤ 1000).The second line contains
n
space-separated integers
(0 ≤ ≤ 100).The third line contains
n
space-separated integers
(0 ≤ ≤ 100). Output
The program should print the maximum length of the common subarray.
Examples
Input | Output |
4
1 2 4 2
0 4 2 1 | 2 |
3
5 5 5
5 5 5 | 3 |
Explanation
- The longest common subarray is
4 2
that’s common in both of the given arrays ⇒ 2 length
- The two arrays are equal ⇒ the longest common subarray is the given array itself ⇒ 3 length
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB