718.Maximum Length of Repeated Subarray

Tags: Medium Dynamic programming

Links: https://leetcode.com/problems/maximum-length-of-repeated-subarray/

---

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. 1 <= len(A), len(B) <= 1000
2. 0 <= A[i], B[i] < 100

---

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = A.size(), n = B.size();
        vector<vector<int>> d(m + 1, vector<int>(n + 1, 0));
        int res = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                d[i][j] = (A[i - 1] == B[j - 1]) ? d[i - 1][j - 1] + 1 : 0;
                res = max(res, d[i][j]);
            }
        }

        return res;
    }
};

注意和动态规划里的LCS进行区分，LCS里的是子序列，可以不连续，但是本题要求是子数组，需要连续，仍然是利用动态规划，d[i]j[j]代表数组A的前ii个数字和数组B的前j个数字的最长连续公共子数组的长度，状态转移方程，因为要求连续，如果A[I-1]和B[j - 1]相同，那么就是d[i - 1][j - 1] + 1，否则就是0。