最长重复子数组

一、题目描述

题目链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

 

二、题目分析

这道题是一道典型的动态规划题。

使用一个二位数组dp[i][j]来表示两个数组在[i: ]和[j: ]的最长公共前缀，每次公共前缀的计算与后一个位置相关，因此我们做一个从后往前的dp。看代码应该比较明晰。

 

三、代码

链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zui-chang-zhong-fu-zi-shu-zu-by-leetcode-solution/

class Solution {
    public int findLength(int[] A, int[] B) {
        int n = A.length, m = B.length;
        int[][] dp = new int[n + 1][m + 1];
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }
}