718. Maximum Length of Repeated Subarray

Question

LeetCode Problem

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 <= 1000
• 0 <= nums1[i], nums2[i] <= 100

Solutions

Use dynamic programming

• dp[i][j]定義：在a長度為i 與b長度為j的最長重複子數組
• 遞推公式：if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-i] + 1

int findLength(vector<int>& a, vector<int>&b) {
	int m = a.size();
	int n = b.size();
	it (m == 0 || n == 0) return 0;
	vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
	int maxLen = 0;
	for (int i = 1; i <= m; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (a[i-1] == b[j-1]) {
				dp[i][j] = dp[i-1][j-1] + 1;
				maxLen = max(maxLen, dp[i][j]);
			} else {
				dp[i][j] = 0;
			}
		}
	}
	return maxLen;
}