718. Maximum Length of Repeated Subarray
Medium51.3% acceptance360,312 / 702,881 submissions
Asked by 6 companies
Topics
Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.
Example 1:
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3,2,1].
Example 2:
Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] Output: 5 Explanation: The repeated subarray with maximum length is [0,0,0,0,0].
Constraints:
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 100
Hints
Hint 1
Use dynamic programming. dp[i][j] will be the longest common prefix of A[i:] and B[j:].
Hint 2
The answer is max(dp[i][j]) over all i, j.