最长重复子数组

    技术2022-07-10  130

    给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

    示例 1:

    输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。 说明:

    1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    class Solution { public: int findLength(vector<int>& A, vector<int>& B) { int na = A.size(), nb = B.size(); vector<vector<int>>dp(na+1,vector<int>(nb+1,0)); int res=0; for(int i=na-1;i>=0;--i){ for(int j=nb-1;j>=0;--j){ if(A[i]==B[j]){ dp[i][j] = dp[i+1][j+1]+1; }else{ dp[i][j] = 0; } res = max(res,dp[i][j]); } } return res; } };
    Processed: 0.011, SQL: 9