leetcode(5)

leetcode(5)

718. Maximum Length of Repeated Subarray

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

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

一个全局变量res,一个数组用来记录当前最大子串长度,两个指针,一首一尾(如果双首或双尾会造成数据擦除)。

eg:

【1,2,3,2,1】

【3,2,1,4,7】

i=4,j=0            dp[0]=0              i=3,j=0              dp[0]=0           i=2,j=0             dp[0]=3

i=4,j=1             dp[1]=0              i=3,j=1               dp[1]=2            i=2,j=1             dp[1]=0

i=4,j=2            dp[2]=1               i=3,j=2              dp[2]=0           i=2,j=2             dp[2]=0     …

i=4,j=3            dp[3]=0              i=3,j=3              dp[3]=0            i=2,j=3            dp[3]=0

i=4,j=4             dp[4]=0             i=3,j=4              dp[4]=0            i=2,j=4             dp[4]=0

res每次记录dp的最大值




So BadJust So SoGoodCoolPretty Cool (还没人评过分呢!)
Loading...

发表评论

电子邮件地址不会被公开。 必填项已用*标注