题目

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例 1:

输入: 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

解题思路

和最长公共子序列非常相似，但是本题需要求子数组而不是子序列。子数组需要是连续的，所以不能像子序列那样保存最大值，dp[i][j]的含义变为text1[:i]和text2[:j]从后向前的相同字符个数了。转移方程因此变为： $$\begin{array}{r}dp[i][j]=\{\begin{array}{ll}dp[i-1][j-1]+1,& iftext1[i]==text2[j]\\ 0,& iftext1[i]\ne text2[j]\end{array}\end{array}$$

最后我们在构建dp的过程中，保留最大值即可

时间复杂度为$o(m\ast n)$

代码

class Solution: def findLength(self, A: List[int], B: List[int]) -> int: dp = [[0] * (len(A) + 1) for _ in range(len(B) + 1)] max_cnt = 0 for i in range(1, len(B) + 1): for j in range(1, len(A) + 1): if B[i - 1] == A[j - 1]: dp[i][j] = 1 + dp[i - 1][j - 1] max_cnt = max(max_cnt, dp[i][j]) return max_cnt