leetcode 718. Maximum Length of Repeated Subarray 最长公共子串 + 动态规划DP

梦里梦外; 2022-06-03 08:54 176阅读 0赞

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

本题就是寻找最长的公共子串

建议和[leetcode 583. Delete Operation for Two Strings 最长公共子串 + DP动态规划][leetcode 583. Delete Operation for Two Strings _ _ DP] 和 [leetcode 712. Minimum ASCII Delete Sum for Two Strings 动态规划DP][leetcode 712. Minimum ASCII Delete Sum for Two Strings _DP] 一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int findLength(vector<int>& a, vector<int>& b) 
        {
            int m = a.size(), n = b.size();
            vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    
            int res = 0;
            for (int i = 1; i <= m; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    if (a[i - 1] == b[j - 1])
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    else
                        dp[i][j] = 0;
                    res = max(res, dp[i][j]);
                }
            }
            return res;
        }
    };

[leetcode 583. Delete Operation for Two Strings _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/78836754
[leetcode 712. Minimum ASCII Delete Sum for Two Strings _DP]: http://blog.csdn.net/jackzhang_123/article/details/78883782