[LeetCode] Problem 718 - Maximum Length of Repeated Subarray

Posted on | In ,

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// dp[i][j] = dp[i - 1][j - 1] + 1, A[i] = B[j]
public int findLength(int[] A, int[] B) {
    if (A.length < B.length)
        return findLength(B, A);

    int max = 0;
    int m = A.length;
    int n = B.length;
    int[] dp = new int[n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = n; j >= 1; j--) {
            if (A[i - 1] == B[j - 1]) {
                dp[j] = dp[j - 1] + 1;
                max = Math.max(max, dp[j]);
            }
            else 
                dp[j] = 0;
        }
    }

    return max;
}