718. Maximum Length of Repeated Subarray

开源项目
1

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

思路

使用动态规划的思想，新的相同子数组长度依赖上一次的相同子数组长度，声明数组用来存储每一次结果，遍历A和B进行计算。

python

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        # 声明二维数组
        dp = [[0 for _ in range(len(B)+1)] for _ in range(len(A) + 1) ]
        for i in range(1, len(A)+1):
            for j in range(1, len(B)+1):
                if A[i-1] == B[j-1]:
                    # 如果相同，则二维数组在之前的结果加1
                    dp[i][j] = dp[i-1][j-1] + 1
        # 返回数组中最大的数
        return max(max(row) for row in dp)