最长重复子数组
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度
1
2
3
| 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
|
思路：定义dp[i][j]数组为第一个数组i索引与第二个数组j索引结尾子数组最大公共长度。同时存在状态转移关系：
dp[i][j] = dp[i-1][j-1]+1 when nums1[i] == nums2[j] and i != 0 and j != 0
dp[i][j] = 1 when nums1[i] == nums2[j] and i==0 || j == 0
dp[i][j] = 0 when nums1[i] != nums2[j] and i==0 || j == 0
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
int max = 0;
public int findLength(int[] nums1, int[] nums2) {
int l1 = nums1.length;
int l2 = nums2.length;
int[][] dp = new int[l1][l2];
for(int i = 0; i < l1; i++) {
for(int j = 0; j < l2; j++) {
boolean csame = nums1[i] == nums2[j];
if(i == 0 || j == 0) {
dp[i][j] = csame ? 1 : 0;
} else {
if(csame) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = 0;
}
}
max = Math.max(dp[i][j], max);
}
}
return max;
}
}
|