# Leetcode: Maximum Length of Repeated Subarray

Maximum Length of Repeated Subarray

Similar Problems:

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 <= len(A), len(B) <= 1000
• 0 <= A[i], B[i] < 100

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution1: dp: Time O(n*m), Space O(n*m)
```// Blog link: https://code.dennyzhang.com/maximum-length-of-repeated-subarray
// Basic Ideas: dynamic programming
//
//   Let's say the common subarray starts with A[i] and B[j]
//   If A[i] == B[j], then dp[i][j] = dp[i]
//   Otherwise dp[i][j] = 0
//  So from right to left, we get dp[][]
//  Then find the maximum
//
// To save the code of base case, we add an extra line and column
//
// Complexity: Time O(n*m), Space O(n*m)
func findLength(A []int, B []int) int {
len_a, len_b := len(A), len(B)
dp := make([][]int, len_a+1)
for i:=0; i<len_a+1; i++ { dp[i] = make([]int, len_b+1) }
// A: [1,2,3,2,1]
// B: [3,2,1,4]
res := 0
// dp
for i := len_a-1; i>=0; i-- {
for j := len_b-1; j>=0; j-- {
if A[i] == B[j] {
dp[i][j] = dp[i+1][j+1] + 1
if dp[i][j] > res { res = dp[i][j]}
}
}
}
return res
}
```

• – Solution2: dp: Time O(n*m), Space O(n+m)
```// Blog link: https://code.dennyzhang.com/maximum-length-of-repeated-subarray
//
// From right to left
//
// dp[i][j] only depend on dp[i+1][j+1].
// So Instead of 2D array, we use 2 1D array
//
// Complexity: Time O(n*m), Space O(m)
func findLength(A []int, B []int) int {
len_a, len_b := len(A), len(B)
dp := make([]int, len_b+1)
// A: [1,2,3,2,1]
// B: [3,2,1,4]
res := 0
// dp
for i := len_a-1; i>=0; i-- {
dp2 := make([]int, len(dp))
copy(dp2, dp)
for j := len_b-1; j>=0; j-- {
if A[i] == B[j] {
dp2[j] = dp[j+1] + 1
if dp2[j]> res { res = dp2[j] }
}
}
copy(dp, dp2)
}
return res
}
```

Share It, If You Like It.