718 Maximum Length of Repeated Subarray

718. Maximum Length of Repeated Subarray

1. Question

Given two integer arraysAandB, 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

2. Implementation

(1) DP

思路: 这题其实和求Longest Common Substring是一样的，所以可以直接套用模板写

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

3. Time & Space Complexity

DP：时间复杂度O(n), 空间复杂度O(n)