718. Maximum Length of Repeated Subarray | Leetcode | Dynamic programming

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

 

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 100

solution :

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<int>(size2+1 , 0));

        int max = INT_MIN;

        for(int i = 0 ; i < size1; i++)

        {

            for(int j = 0 ; j < size2 ; j++)

            {    if(i==0 && nums1[i] == nums2[j])

                   dp[i][j] =1;

                 else

                 if(j == 0 && nums1[i] == nums2[j] )

                     dp[i][j] =1;

                 else

                 if(nums1[i] == nums2[j])

                     dp[i][j] = dp[i-1][j-1] +1;

                if(max < dp[i][j])

                    max = dp[i][j];

            }

        }

        return max;

    }

};