Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.
Example
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 <= len(A), len(B) <= 1000
- 0 <= A[i], B[i] < 100
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
public int (int[] A, int[] B) { if (A.length < B.length) return findLength(B, A);
int max = 0; int m = A.length; int n = B.length; int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) { for (int j = n; j >= 1; j--) { if (A[i - 1] == B[j - 1]) { dp[j] = dp[j - 1] + 1; max = Math.max(max, dp[j]); } else dp[j] = 0; } }
return max; }
|
近期评论