题目描述
Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.
Example1:
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
解题思路
- 对于这种求极值的问题，动态规划 Dynamic Programming 一直都是一个很好的选择，这里使用一个二维的 DP 数组，其中 dp[i][j] 表示数组A的前i个数字和数组B的前j个数字的最长子数组的长度，如果 dp[i][j] 不为0，则A中第i个数组和B中第j个数字必须相等，比对于这两个数组 [1,2,2] 和 [3,1,2]，dp 数组为：
3 1 2 1 0 1 0 2 0 0 2 2 0 0 1
- 注意观察，dp 值不为0的地方，都是当 A[i] == B[j] 的地方，而且还要加上左上方的 dp 值，即 dp[i-1][j-1]，所以当前的 dp[i][j] 就等于 dp[i-1][j-1] + 1，而一旦 A[i] != B[j] 时，直接赋值为0，不用多想，因为子数组是要连续的，一旦不匹配了，就不能再增加长度了。每次算出一个 dp 值，都要用来更新结果 res，这样就能得到最长相同子数组的长度了
- 递推关系式 dp[i][j] = dp[i - 1][j - 1] + 1 (if A[i - 1] == B[j - 1]) else dp[i][j] = 0
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int row = A.size();
int col = B.size();
vector<vector<int>> dp(row + 1, vector<int>(col + 1, 0));
int res = 0;
for(int i = 1; i <= row; i++){
for(int j = 1; j <= col; j++){
if(A[i - 1] == B[j - 1]){
dp[i][j] = dp[i - 1][j - 1] + 1;
}else{
dp[i][j] = 0;
}
res = max(dp[i][j], res);
}
}
return res;
}
};
