# 718. Maximum Length of Repeated Subarray
Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.
Example:
Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation:
The repeated subarray with maximum length is [3, 2, 1].
# Solution
Approach 1: DP.
# Code (Python)
Approach 1:
def findLength(self, A: List[int], B: List[int]) -> int:
# max_len[i][j]: max length for subarrays ending with A[i] and B[j]
max_len = [[0 for _ in range(len(A))] for _ in range(len(B))]
for i in range(len(A)):
max_len[i][0] = 1 if A[i] == B[0] else 0
for j in range(1, len(B)):
max_len[0][j] = 1 if A[0] == B[j] else 0
for i in range(1, len(A)):
for j in range(1, len(B)):
if A[i] == B[j]:
max_len[i][j] = max_len[i-1][j-1] + 1
return max(map(max, max_len))
# space can be optimized to 1D
# Code (C++)
Approach 1:
Approach 2: