Tìm chuỗi Fibonacci trong mảng dùng JavaScript

Dãy Fibonacci

Một dãy X₁, X₂, ..., Xₙ là Fibonacci nếu:

• n ≥ 3
• Xᵢ + Xᵢ₊₁ = Xᵢ₊₂ với mọi i + 2 ≤ n

Vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào một mảng số arr làm đối số duy nhất. Hàm phải tìm và trả về độ dài của dãy con Fibonacci dài nhất tồn tại trong mảng arr. Dãy con được lấy từ dãy khác bằng cách xóa bất kỳ số lượng phần tử nào (kể cả không xóa) mà không thay đổi thứ tự các phần tử còn lại.

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

Đầu vào

const arr = [1, 3, 7, 11, 14, 25, 39];

Đầu ra

const output = 5;

Giải thích

Vì dãy con Fibonacci dài nhất là [3, 11, 14, 25, 39].

Ví dụ

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

const arr = [1, 3, 7, 11, 14, 25, 39];
const longestFibonacci = (arr = []) => {
  const map = arr.reduce((acc, num, index) => {
    acc[num] = index;
    return acc;
  }, {});
  const memo = arr.map(() => arr.map(() => 0));
  let max = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      const a = arr[i];
      const b = arr[j];
      const index = map[b - a];
      if (index < i) {
        memo[i][j] = memo[index][i] + 1;
      }
      max = Math.max(max, memo[i][j]);
    }
  }
  return max > 0 ? max + 2 : 0;
};
console.log(longestFibonacci(arr));

Kết quả

5