原题链接在这里:https://leetcode.com/problems/maximum-length-of-repeated-subarray/
题目:
Given two integer arrays A
and B
, return the maximum length of an subarray that appears in both arrays.
Example 1:
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
题解:
The subarray must be continuous.
dp[i][j] denotes the maximum length of repeated subarray between A up to index i and B up to index j.
if(A[i] == B[j]) dp[i][j] = dp[i-1][j-1]+1.
if(A[i] != B[j]) d[i][j] = 0.
Time Complexity: O(m*n).
Space: O(m*n).
AC Java:
1 class Solution { 2 public int findLength(int[] A, int[] B) { 3 if(A == null || A.length == 0 || B == null || B.length == 0){ 4 return 0; 5 } 6 7 int m = A.length; 8 int n = B.length; 9 int [][] dp = new int[m+1][n+1]; 10 int res = 0; 11 for(int i = 1; i<=m; i++){ 12 for(int j = 1; j<=n; j++){ 13 if(A[i-1] == B[j-1]){ 14 dp[i][j] = dp[i-1][j-1]+1; 15 res = Math.max(res, dp[i][j]); 16 } 17 } 18 } 19 20 return res; 21 } 22 }
类似Longest Common Subsequence, Minimum ASCII Delete Sum for Two Strings, Delete Operation for Two Strings.