Maximum Length of Repeated Subarray

Description

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(javascript)

/** 暴力解法 O(n^3)
 * @param {number[]} A
 * @param {number[]} B
 * @return {number}
 */
// const findLength = function (A = [], B = []) {
//   let max = 0
//   for (let i = 0; i < A.length; i++) {
//     for (let j = 0; j < B.length; j++) {
//       let count = 0
//       while (A[i + count] === B[j + count] && A[i + count] !== undefined) {
//         count += 1
//       }
//       max = Math.max(max, count)
//     }
//   }
//   return max
// }

//  自底向上的 DP
const findLength = function (A = [], B = []) {
  const dp = new Array(A.length + 1).fill(0).map(() => new Array(B.length + 1).fill(0))
  for (let i = A.length - 1; i >= 0; i--) {
    for (let j = B.length - 1; j >= 0; j--) {
      if (A[i] === B[j]) {
        dp[i][j] = dp[i + 1][j + 1] + 1
      } else {
        dp[i][j] = 0
      }
    }
  }
  return dp.reduce((acc, items) => Math.max(acc, ...items), 0)
}