Tìm độ dài lớn nhất mảng con chung trong JavaScript

Vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào hai mảng chữ arr1 và arr2 làm đối số thứ nhất và thứ hai. Hàm phải trả về độ dài lớn nhất của một mảng con xuất hiện trong cả hai mảng.

Ví dụ, nếu đầu vào là:

Đầu vào

const arr1 = [1, 2, 3, 2, 1];
const arr2 = [3, 2, 1, 4, 7];

Đầu ra

const output = 3;

Giải thích

Mảng con lặp lại dài nhất là [3, 2, 1].

Ví dụ

Dưới đây là mã thực hiện:

const arr1 = [1, 2, 3, 2, 1];
const arr2 = [3, 2, 1, 4, 7];
const maximumLength = (arr1 = [], arr2 = []) => {
  const dp = new Array(arr1.length + 1).fill(0).map(() => new Array(arr2.length + 1).fill(0));
  for (let i = arr1.length - 1; i >= 0; i--) {
    for (let j = arr2.length - 1; j >= 0; j--) {
      if (arr1[i] === arr2[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);
};
console.log(maximumLength(arr1, arr2));

Kết quả

3