718_最长重复子数组

类型：数组

• 718. 最长重复子数组 💛 ⭐

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

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

  输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释：长度最长的公共子数组是 [3, 2, 1] 。

  💡 动态规划

  此题动态规划解法的妙处在于从后往前规划。

  令 dp[i][j] 表示 A[i:] 和 B[j:] 的最长公共前缀，如果 A[i] == B[j]，那么 dp[i][j] = dp[i + 1][j + 1] + 1，否则 dp[i][j] = 0。我们倒过来，从后往前，首先计算 dp[len(A) - 1][len(B) - 1]，最后计算 dp[0][0]。

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

  时间复杂度：O(mn)，空间复杂度：O(mn)