# 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: