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

``````class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int m = A.size(), n = B.size(), res = 0;
for (int offset = 0; offset < m; ++offset) {
for (int i = offset, j = 0; i < m && j < n;) {
int cnt = 0;
while (i < m && j < n && A[i++] == B[j++]) ++cnt;
res = max(res, cnt);
}
}
for (int offset = 0; offset < n; ++offset) {
for (int i = 0, j = offset; i < m && j < n;) {
int cnt = 0;
while (i < m && j < n && A[i++] == B[j++]) ++cnt;
res = max(res, cnt);
}
}
return res;
}
};
``````

``````class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
string strA = stringify(A), strB = stringify(B);
int left = 0, right = min(A.size(), B.size()) + 1;
while (left < right) {
int mid = (left + right) / 2;
if (helper(strA, strB, mid)) left = mid + 1;
else right = mid;
}
return right - 1;
}
bool helper(string& strA, string& strB, int len) {
unordered_set<string> st;
for (int i = 0, j = len; j <= strA.size(); ++i, ++j) {
st.insert(strA.substr(i, j - i));
}
for (int i = 0, j = len; j <= strB.size(); ++i, ++j) {
if (st.count(strB.substr(i, j - i))) return true;
}
return false;
}
string stringify(vector<int>& nums) {
string res;
for (int num : nums) res += num;
return res;
}
};
``````

``````  3 1 2
1 0 1 0
2 0 0 2
2 0 0 1
``````

``````class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int res = 0, m = A.size(), n = B.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
dp[i][j] = (A[i - 1] == B[j - 1]) ? dp[i - 1][j - 1] + 1 : 0;
res = max(res, dp[i][j]);
}
}
return res;
}
};
``````

Follow up：在开始时，博主提到了要跟最长相同子序列 Longest Common Subsequence 区分开来，虽然 LeetCode 没有直接求最大相同子序列的题，但有几道题利用到了求该问题的思想，比如 Delete Operation for Two Strings 和 Minimum ASCII Delete Sum for Two Strings 等，详细讨论请参见评论区一楼 :)

Github 同步地址：

https://github.com/grandyang/leetcode/issues/718

Minimum Size Subarray Sum

https://leetcode.com/problems/maximum-length-of-repeated-subarray/

https://leetcode.com/problems/maximum-length-of-repeated-subarray/discuss/109068/JavaC%2B%2B-Clean-Code-8-lines

https://leetcode.com/problems/maximum-length-of-repeated-subarray/discuss/109039/Concise-Java-DP%3A-Same-idea-of-Longest-Common-Substring

https://leetcode.com/problems/maximum-length-of-repeated-subarray/discuss/109033/Solution-1%3A-DP-O(n2)-with-O(n)-space-Solution-2%3A-Stringify

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation