题目简介：
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例 1:
1
2
3
4
5
6
| 输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。
|
说明:
1 <= len(A), len(B) <= 10000 <= A[i], B[i] < 100
思路：
使用动态规划的思想，d[i][j]代表以A[i]与B[j]为结尾的公共最长子序列。
当A[i] != B[j]时，dp[i][j] == 0
当A[i] == B[j]时，dp[i][j] == dp[i - 1][j - 1] + 1，即之前的公共最长子序列 + 1。
最后返回dp[i][j]中的最大值即可。
tip:
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
vector<vector<int>> dp(A.size(), vector<int>(B.size(), 0));
int Max_len = 0;
for(int j = 0; j < B.size(); j++){
dp[0][j] = (A[0] == B[j]) ? 1 : 0;
Max_len = max(Max_len, dp[0][j]);
}
for(int i = 0; i < A.size(); i++){
dp[i][0] = (A[i] == B[0]) ? 1 : 0;
Max_len = max(Max_len, dp[i][0]);
}
for(int i = 1; i < A.size(); i++){
for(int j = 1; j < B.size(); j++){
if(A[i] == B[j]){
dp[i][j] = dp[i - 1][j - 1] + 1;
Max_len = max(Max_len, dp[i][j]);
}
else
dp[i][j] = 0;
}
}
return Max_len;
}
};
|
