718. Maximum Length of Repeated Subarray

最一开始接触到这个题，想到的是KMP算法2333； 然后想到的是string.h：A中所有子串去B里找； 发现不是字符串而是数组，故暴力法变得更为简单。

暴力法

int findLength(int* A, int ASize, int* B, int BSize){ int i,j; int len = 0; int maxlen = 0; for(i = 0; i < ASize; i++){ for(j = 0; j < BSize; j++){ if(A[i] == B[j]){ len = 1; while(((i + len) < ASize)&&((j + len) < BSize)&&(A[i + len] == B[j + len])){ len++; } if(len > maxlen) maxlen = len; } } } return maxlen; }

然后这个方法由于过于暴力，就： 所以去学习DP（Dynamic Programming，动态规划）解法。

DP

int findLength(int* A, int ASize, int* B, int BSize){ int dp[ASize][BSize]; int i,j; for(i = 0; i < ASize; i++) for(j = 0; j < BSize; j++) dp[i][j] = 0; int max = 0; for(i = 0; i < ASize; i++){ for(j = 0; j < BSize; j++){ if(A[i] == B[j]){ if(i == 0 || j == 0) dp[i][j] = 1; else dp[i][j] = dp[i-1][j-1] + 1; } if(max < dp[i][j]) max = dp[i][j]; } } return max; }