Algorithm
Problem Name: 718. Maximum Length of Repeated Subarray
Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.
Example 1:
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3,2,1].
Example 2:
Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] Output: 5 Explanation: The repeated subarray with maximum length is [0,0,0,0,0].
Constraints:
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 100
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
// dp[i][j] is the maximum length of subarray ending with A[i] and B[j]
// dp[i][j] = (A[i] == B[j]) ? dp[i - 1][j - 1] + 1 : 0;
int m = A.size(), n = B.size();
vector < vector<int>>dp(m, vector<int>(n));
int maxlen = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++){
if(i == 0 || j == 0) dp[i][j] = (A[i] == B[j]);
else dp[i][j] = (A[i] == B[j]) ? dp[i - 1][j - 1] + 1 : 0;
maxlen = max(maxlen, dp[i][j]);
}
return maxlen;
}
};
Input
nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output
5
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int result = 0;
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
for (int i = nums1.length - 1; i >= 0; i--) {
for (int j = nums2.length - 1; j >= 0; j--) {
if (nums1[i] == nums2[j]) {
dp[i][j] = dp[i + 1][j + 1] + 1;
result = Math.max(result, dp[i][j]);
}
}
}
return result;
}
}
Input
nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output
5
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const findLength = function(A, B) {
let ans = 0;
let memo = [];
for (let i = 0; i < A.length + 1; i++) {
memo[i] = Array(B.length + 1).fill(0);
}
for (let i = A.length - 1; i >= 0; --i) {
for (let j = B.length - 1; j >= 0; --j) {
if (A[i] == B[j]) {
memo[i][j] = memo[i + 1][j + 1] + 1;
if (ans < memo[i][j]) ans = memo[i][j];
}
}
}
return ans;
};
Input
nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output
3
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findLength(self, A, B):
A, res, sub = "X%sX" % "X".join(map(str, A)), 0, "X"
for num in B:
sub += str(num) + "X"
if sub in A: res += 1
else: sub = sub[sub[1:].index("X") + 1:]
return res
Input
nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output
3