28. Maximum Length of Repeated Subarray

Similar to maximum length repeated substring

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].

Solution: (DP)

class Solution
{
public:
    int findLength(vector<int> &A, vector<int> &B)
    {

        int n = A.size();
        int m = B.size();
        int max = 0;
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        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;
                    if (dp[i][j] > max)
                    {
                        max = dp[i][j];
                    }
                }
            }
        }

        return max;
    }
};

Time Complexity: O(n * m) Space Complexity: O(n * m)