最长重复子数组

发表于 分类于 阅读次数：

最长重复子数组（难度：中等）

1

方法：动态规划

作者：LeetCode 链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zui-chang-zhong-fu-zi-shu-zu-by-leetcode/ 来源：力扣（LeetCode）

设 dp[i][j]为 A[i:] 和 B[j:] 的最长公共前缀，那么答案为所有 dp[i][j] 中的最大值 max(dp[i][j])。若 A[i] == B[j]，状态转移方程为 dp[i][j] = dp[i + 1][j + 1] + 1，否则为 dp[i][j] = 0。

复杂度分析

时间复杂度：O(M*N)，其中 M和 N是数组 A 和 B 的长度。 空间复杂度：O(M*N)，即为数组 dp 使用的空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findLength(int[] A, int[] B) {
        int[][] dp = new int[A.length+1][B.length+1]; // 长度加1是为了后面的dp[i+1][j+1]
        int res = 0;
        for(int i = A.length-1; i>=0; i--){
            for(int j = B.length-1; j>=0; j--){
                if(A[i] == B[j])
                    dp[i][j] = dp[i+1][j+1] + 1;
                res = Math.max(res,dp[i][j]);
            }
        }
        return res;
    }
}
2