718 Maximum Length of Repeated Subarray

Given two integer arraysAandB, 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

Complexity: O(n*m) time and space

import numpy as np

class Solution:
    def findLength(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: int
        """

        dp_m = np.zeros((len(A) + 1, len(B) + 1), dtype=np.int32)
        for i in range(0, len(A)):
            for j in range(0, len(B)):
                if A[i] == B[j]:
                    dp_m[i+1][j+1] += dp_m[i][j] + 1
        return np.max(dp_m)

Last updated