###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++`

# 718. Maximum Length of Repeated Subarray

## [題目連結:] https://leetcode.com/problems/maximum-length-of-repeated-subarray/

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

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

**Example 2:**

Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5
Explanation: The repeated subarray with maximum length is [0,0,0,0,0].

## 解題想法:
* 此題為給兩組數組，求連續的最長重複數組長度
* 求Longest Common Substring
* 使用DP:
* 定義: dp[i][j]表示nums1[:i]與nums2[:j]的最長subarray
* 轉移方程:
* if nums1[i-1]==nums2[j-1]:
* dp[i][j]=dp[i-1][j-1]+1
* else:
* dp[i][j]=0

* ex:

    nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
    多一行一列存0 所以真正該對應位置是nums1[i-1] nums2[j-1]
        x   3   2   1   4   7
    x   0   0   0   0   0   0
    1   0   0   0   1   0   0   
    2   0   0   1   0   0   0
    3   0   1   0   0   0   0
    2   0   0   2   0   0   0
    1   0   0   0   3   0   0 

## Python:

class Solution(object):
    def findLength(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: int
        """
        m=len(nums1)
        n=len(nums2)
        res=0
        #dp[i][j]表示nums1[:i]與nums2[:j]的最長subarray
        dp=[ [0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                #多一行一列存0 所以真正該對應位置是nums1[i-1] nums2[j-1]
                if nums1[i-1]==nums2[j-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                    res=max(res,dp[i][j])
                else:
                    dp[i][j]=0
        print(dp)
        return res
    
result=Solution()
ans=result.findLength(nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7])
print(ans)

## C++:

#include<bits/stdc++.h>
using namespace std;

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