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 lengthThe 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