传送门 LeeCode 718. 最长重复子数组
与 L C S LCS LCS 不同的是，子数组必须是连续的。 d p [ i ] [ j ] dp[i][j] dp[i][j] 代表以 A i − 1 , B j − 1 A_{i-1},B_{j-1} Ai−1,Bj−1 结尾的最长重复子串长度，则递推式为
d p [ i ] [ j ] = { d p [ i − 1 ] [ j − 1 ] + 1 A [ i − 1 ] = B [ j − 1 ] 0 o t h e r w i s e dp[i][j]=\begin{cases} dp[i-1][j-1]+1 & A[i-1]=B[j-1]\\ 0 & otherwise \end{cases} dp[i][j]={dp[i−1][j−1]+10A[i−1]=B[j−1]otherwise
class Solution { #define maxn 1005 public: int dp[maxn][maxn]; int findLength(vector<int> &A, vector<int> &B) { int na = A.size(), nb = B.size(), res = 0; for (int i = 1; i <= na; i++) { for (int j = 1; j <= nb; j++) { if (A[i - 1] == B[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1, res = max(res, dp[i][j]); } } } return res; } };