[LeetCode] 718. Maximum Length of Repeated Subarray

轉自LeetCode

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

<Solution>

想法如下

• 這題要用 DP 來解。 用 dp[i][j] 代表 A[i] 和 B[j] 有多長的相同 subarry (包含 A[i] 和 B[j])，用 [5, 7, 8] 和 [2, 7, 8] 來舉例

       2  7  8
    0  0  0  0
5   0  0  0  0
7   0  0  1  0
8   0  0  0  2

• 首先，dp = int[A.length + 1][B.length + 1]，且 dp[i][j] = (A[i-1] == B[j-1]) ? dp[i-1][j-1]  + 1 : 0

• 最後的答案，會是 max(dp[i][j])，所以過程中也要順便紀錄最大值

code 如下

Java

Kotlin