# [LeetCode 718. Maximum Length of Repeated Subarray](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3807/)
### Daily challenge Jul 8, 2021 (MEDIAN)

>Given two integer arrays **`nums1`** and **`nums2`**, return the maximum length of a subarray that appears in **both** arrays.

:::info
**Example 1:**
**Input:** nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
**Output:** 3
**Explanation:** The repeated subarray with maximum length is [3,2,1].
:::

:::info
**Example 2:**
**Input:** nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
**Output:** 5
:::

:::warning
**Constraints:**
* 1 <= nums1.length, nums2.length <= 1000
* 0 <= nums1[i], nums2[i] <= 100
:::

---

### Approach 1 : DP :book:
**`348 ms`** **`O(M * N)`** *where M, N are the length of A, B.*

>Let **`dp[i][j]`** be the longest common prefix of **`A[i:]`** and **`B[j:]`**. Whenever **`A[i] == B[j]`**, we know **`dp[i][j] = dp[i+1][j+1] + 1`**. Also, the answer is **`max(dp[i][j])`** over all *`i, j`*.

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int size1 = nums1.size();
        int size2 = nums2.size();
        
        vector<vector<int> > dp(size1+1, vector(size2+1, 0));
        int MAX = INT_MIN;
        
        for(int i=size1-1; i>=0; i--){
            for(int j=size2-1; j>=0; j--){
                dp[i][j] = (nums1[i] == nums2[j]) ? dp[i+1][j+1]+1 : 0;
             
                MAX = max(MAX, dp[i][j]);
            }
        }
        
        return MAX;
    }
};