LWC 56：718. Maximum Length of Repeated Subarray
LWC 56：718. Maximum Length of Repeated Subarray
用户1147447
发布于 2018-01-02 10:46:45
发布于 2018-01-02 10:46:45
LWC 56：718. Maximum Length of Repeated Subarray
传送门：718. Maximum Length of Repeated Subarray
Problem:
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的问题规模变成n-1，和B求出最长subarray长度，或者把B的问题规模变成m-1，和A求出最长subarray。
遇到相等该如何操作，自然在子问题n-1，和m-1基础上+1，（问题的定义如下：给定A和B的末区间i和j，返回A[0,…,i]和B[0,…,j]中以i和j结尾的最长subArray长度），
所以有如下递归式：
f(A, B, i, j) = 1 + f(A, B, i - 1, j - 1); if (A[i] == B[j])
or:
f(A, B, i, j) = 0;此时就可以用数组dp记录每个状态的最长subArray长度，并在过程中不断更新max。
代码如下：
public int findLength(int[] A, int[] B) {
max = 0;
int n = A.length;
int m = B.length;
dp = new int[n + 1][m + 1];
for (int i = 0; i < n + 1; ++i) {
for (int j = 0; j < m + 1; ++j) {
dp[i][j] = -1;
}
}
dfs(A, B, n - 1, m - 1);
return max;
}
int[][] dp;
int max = 0;
int dfs(int[] A, int[] B, int n, int m) {
if (n == -1 || m == -1) return 0;
if (dp[n][m] >= 0) return dp[n][m];
dfs(A, B, n - 1, m);
dfs(A, B, n, m - 1);
if (A[n] == B[m]) {
int ans = 1;
int sub = dfs(A, B, n - 1, m - 1);
max = Math.max(max, ans + sub);
dp[n][m] = ans + sub;
return ans + sub;
}
else {
dp[n][m] = 0;
return 0;
}
}注意此处，0也是可能的一种答案，所以DP初始化为-1，否则超时。
递推版本（动态规划）：
public int findLength(int[] A, int[] B) {
int n = A.length;
int m = B.length;
int max = 0;
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
dp[i][j] = 0;
}
max = Math.max(dp[i][j], max);
}
}
return max;
} 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-10-29 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录