Formatted question description: https://leetcode.ca/all/718.html

# 718. Maximum Length of Repeated Subarray

Medium

## Description

Given two integer arrays A and B, return the maximum length of a subarray that appears in both arrays.

Example 1:

Input:

A: [1,2,3,2,1]

B: [3,2,1,4,7]

Output: 3

*8Explanation: **

The repeated subarray with maximum length is [3, 2, 1].

Note:

1. 1 <= len(A), len(B) <= 1000
2. 0 <= A[i], B[i] < 100

## Solution

Use dynamic programming. Create a 2D array dp of A.length + 1 rows and B.length + 1 columns, where dp[i][j] represents the maximum length of repeated subarray of the two subarray A[i..] and B[j..].

Initially, all elements in dp are 0. For i from A.length - 1 to 0 and j from B.length - 1 to 0, if A[i] == B[j], then there is a repeated subarray that starts from index i in A and index j in B, so update dp[i][j] = dp[i + 1][j + 1] + 1, and update the maximum length of a repeated subarray. Finally, return the maximum length of a repeated subarray.

Java

Java

class Solution {
public int findLength(int[] A, int[] B) {
int maxLength = 0;
int length1 = A.length, length2 = B.length;
int[][] dp = new int[length1 + 1][length2 + 1];
for (int i = length1 - 1; i >= 0; i--) {
for (int j = length2 - 1; j >= 0; j--) {
if (A[i] == B[j]) {
dp[i][j] = dp[i + 1][j + 1] + 1;
maxLength = Math.max(maxLength, dp[i][j]);
}
}
}
return maxLength;
}
}