> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/binary-search/718-maximum-length-of-repeated-subarray.md).

# 718     Maximum Length of Repeated Subarray

## 718. [Maximum Length of Repeated Subarray](https://leetcode.com/problems/maximum-length-of-repeated-subarray/description/)

## 1. Question

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

**Example 1:**

```
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].
```

**Note:**

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

## 2. Implementation

**(1) DP**

思路: 这题其实和求Longest Common Substring是一样的，所以可以直接套用模板写

```java
class Solution {
    public int findLength(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        int[][] dp = new int[m + 1][n + 1];
        int maxLen = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                    maxLen = Math.max(maxLen, dp[i][j]);
                }
            }
        }
        return maxLen;
    }
}
```

## 3. Time & Space Complexity

**DP：**&#x65F6;间复杂度O(n), 空间复杂度O(n)