这道题时最长公共子序列的一个变种，对这道题目印象非常的深，原因是以前面试的时候被这道题目卡住了，老规矩我们先尝试暴力破解方法。

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int maxlen = 0;
        for(int i = 0;i < A.size();i++)
        {
            for(int j = 0;j < B.size();j++)
            {
                if(A[i] == B[j])
                {
                    int k = 1;
                    while((i + k < A.size())&&(j + k < B.size()) 
                        &&(A[i + k] == B[j + k])){
                        k += 1;
                    }
                    maxlen = max(maxlen,k);
                }
            }
        }

        return maxlen;
    }
};

运行结果:

Time Limit Exceeded
Details 
Last executed input
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0View All

一般运行超时表示我们思路是对的，但是性能不行，可以点开detail看到我们已经pass了一半用例，下面我们尝试优化算法。
需要一提的是上面的暴力破解如果忽略对参数合法性的判断，会导致运行时错误(vector访问越界)。
使用动态规划算法解决该问题，难点在于状态转移方程：
dp[i][j] = dp[i-1][j-1]+1 if A[i]==B[j] else 0
dp[i][j] 表示以A[i]结尾 B[j]结尾的数组最长的公共序列长度，如果A[i]和B[j]不相等，那么公共长度为0.（满足以A[i] B[i结尾，最后A[i]] B[j]不相等），如果A[i]和B[j]相等转移到dp[i-1][j-1],这一点相对来说比较好理解。

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int m = A.size(),n = B.size();
        int dp[m + 1][n + 1];
        memset(dp,0,sizeof(int)*(m+1)*(n+1));
        int maxlen = 0;
        for(int i = 0; i < m;i++) {
            for(int j = 0;j < n;j++) {
                if(A[i] == B[j])
                    dp[i][j] = (i == 0 || j == 0) ? 1 : dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = 0;
                
                maxlen = max(maxlen,dp[i][j]);
            }
        }
        return maxlen;
    }
};

运行结果:

Runtime: 160 ms, faster than 91.29% of C++ online submissions for Maximum Length of Repeated Subarray.
Memory Usage: 16 MB, less than 71.61% of C++ online submissions for Maximum Length of Repeated Subarray.