本文共 1851 字，大约阅读时间需要 6 分钟。

题目：

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

解释：

if A[i]==B[j]: 		dp[i][j]=dp[i-1][j-1]+1	else:		dp[i][j]=0	return maxLen

2.如果是subsequence, dp[i][j] 表示A的前i个元素和B的前j个元素构成的子序列所组成的LCS,那么转移方程是

dp[i][0]=0,dp[0][j]=0	if A[i]==B[j]：		dp[i][j]=dp[i-1][j-1]+1	else:		dp[i][j]=max(dp[i-1][j],dp[i][j-1])	#需要注意这里	return dp[m][n]

可是这种解法速度好慢啊，居然要5000ms？？？？

class Solution:    def findLength(self, A, B):        """        :type A: List[int]        :type B: List[int]        :rtype: int        """        m=len(A)        n=len(B)        dp=[[0]*(n+1) for _ in range(m+1)]        maxLen=0        for i in range(1,m+1):            for j in range(1,n+1):                if A[i-1]==B[j-1]:                    dp[i][j]=dp[i-1][j-1]+1                    maxLen=max(maxLen,dp[i][j])                else:                    dp[i][j]=0        return maxLen

c++代码：

class Solution {
   public:    int findLength(vector
   
    & A, vector
    
     & B) {
           int m=A.size();        int n=B.size();        vector
     
      
       > dp(m+1,vector
       
        (n+1,0));        int maxLen=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;                    maxLen=max(maxLen,dp[i][j]);                }             }        }        return maxLen;              }};
       
      
     
    
   

总结：

转载地址：http://iwmcn.baihongyu.com/