题目描述
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
解题思路
先解释一下题目的大概意思。首先A,B是两个整形的数组，我们需要找出一个同时包含在A和B中的子数组，使它的长度最大。这里有个陷阱是题目没有讲清楚的：它描述中的子数组，并不只是单纯的具有和原数组相同的元素，还必须要顺序相同且连续。
换句话说，我们要找出一个同时出现在A和B中的连续的子序列，并且使它的长度最长。首先讲一下最简单的方法：
对于每一个在A中的元素A[i]，从B中的第j个元素开始匹配，直到无法匹配为止。最差的情况是，从A和B是相同的，且所有元素相等，这样，A[0]要做O(n^2) 次计算……显然，这样复杂度很容易上升到O(n^3)，对于长度是1000的A和B而言很容易就会出现超时的情况。
因此，这时我们要用到的是动态规划的算法。考虑动归数组dp，dp[i][j]表示从A[i]和B[j]开始的串的最长匹配。如果A[i]=B[j]时，说明这里存在一个子串，这时我们看下A[i-1]是否等于B[j-1]，若A[i-1]=B[j-1]那么dp[i][j]的长度就是当前子串的长度（1）再加上前一个子串的长度。前一个子串的长度为dp[i-1][j-1]。由此我们可以得到动归方程：
dp[i][j] = dp[i-1][j-1] + 1 if A[i] == B[j]
现在对边界情况讨论：若i-1或者j-1中的其中一个越界，即说明不存在dp[i][j]前的子串，因此长度为0，只需要让:
dp[i][j] = 1 if i == 0 or j == 0
进行到这里，问题大概就能解决了。
时间复杂度分析
遍历一次A和B，复杂度为O(a * b)
空间复杂度分析
dp二维数组，两个维度分别是A和B的长度，因此也是O(a * b)
源码
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int dp[A.size()][B.size()];
memset(dp, 0, sizeof(int) * A.size() * B.size());
int _max = 0;
for (int i = 0; i < A.size(); ++i) {
for (int j = 0; j < B.size(); ++j) {
if (A[i] == B[j]) {
if (i != 0 && j != 0) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = 1;
}
_max = max(dp[i][j], _max);
}
}
}
return _max;
}
};
