718. Maximum Length of Repeated Subarray - cocoder39/coco39_LC GitHub Wiki

718. Maximum Length of Repeated Subarray

dp[i][j]: the maximum Length of Repeated Subarray ends with A[i-1] or B[j-1]

dp[i][j] is the local max instead of global max. With local max, it is easy to get dp[i+1][j+1]. For global max, we can use res = max(res, dp[i][j])

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