给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例：
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。
提示：
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray
参考：
python
# 0718.最长重复子数组
class Solution:
def maxLengthOfSubarr(self, nums1: [int], nums2: [int]) -> int:
"""
动态规划，最大重复子数组-二维数组
1.dp定义及下标
- dp[i][j], 下标i-1结尾的nums1数组，与下标j-1结尾的nums2数组的，最长重复子数组长度
2.递推公式
- dp[i][j] = dp[i-1][j-1] + 1
3.初始化
- dp[0][i] = dp[i][0] = 0
4.遍历顺序
- 先1后2，或者先2后1
:param nums1:
:param nums2:
:return:
"""
dp = [[0]*(len(nums2)+1) for _ in range(len(nums1)+1)]
res = 0
for i in range(1, len(nums1)+1):
for j in range(1, len(nums2)+1):
if nums1[i-1] == nums2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
res = max(res, dp[i][j])
return res
def maxLengthOfSubarr_(self, nums1: [int], nums2: [int]) -> int:
"""
动态规划，最大重复子数组-滚动数组
:param nums1:
:param nums2:
:return:
"""
dp = [0] * (len(nums2)+1)
res = 0
for i in range(1, len(nums1)+1):
for j in range(len(nums2), 0, -1): # 避免重复覆盖
if nums1[i-1] == nums2[j-1]:
dp[j] = dp[j-1] + 1
else:
dp[j] = 0 # update
res = max(res, dp[j])
return res
golang
package dynamicPrograming
// 动态规划-二维数组
func maxLengthOfSubarr(nums1, nums2 []int) int {
dp := make([][]int, len(nums1)+1)
for i:=0;i<=len(nums1);i++ {
dp[i] = make([]int, len(nums2)+1)
}
res := 0
for i:=1;i<=len(nums1);i++ {
for j:=1;j<=len(nums2);j++ {
if nums1[i-1] == nums2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
}
res = max(res, dp[i][j])
}
}
return res
}
// 动态规划-一维数组/滚动数组
func maxLengthOfSubarr_(nums1, nums2 []int) int {
dp := make([]int, len(nums2)+1)
res := 0
for i:=0;i<=len(nums2);i++ {
dp[i] = 0
}
for i:=1;i<=len(nums1);i++ {
for j:=len(nums2);j>=1;j-- {
if nums1[i-1] == nums2[j-1] {
dp[j] = dp[j-1] + 1
} else {
dp[j] = 0
}
res = max(res, dp[j])
}
}
return res
}
func max(a,b int) int {
if a > b {return a}
return b
}