[LeetCode] 718 | Maximum Length of Repeated Subarray | Python

---

문제 링크: https://leetcode.com/problems/maximum-length-of-repeated-subarray/

---

문제

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

---

조건

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 100

---

내 풀이

다이나믹 프로그래밍으로 푼다.

nums1[i-1]과 nums2[j-1]이 같다면 dp[i][j]는 이전 단계인 dp[i-1][j-1]에 1을 더해준다.

---

코드

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        N1, N2 = len(nums1), len(nums2)
        dp = [[0]*(N2+1) for _ in range(N1+1)]
        ans = 0
        
        for i in range(1, N1+1):
            for j in range(1, N2+1):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    ans = max(ans, dp[i][j])
        
        return ans