Tìm chuỗi Fibonacci trong một mảng bằng JavaScript

Trình tự Fibonacci:

Một dãy X_1, X_2, ..., X_n là fibonacci nếu:

n> =3
X_i + X_ {i + 1} =X_ {i + 2} cho tất cả i + 2 <=n

Vấn đề

Chúng tôi được yêu cầu viết một hàm JavaScript nhận một mảng số, arr, làm đối số đầu tiên và duy nhất. Hàm của chúng ta sẽ tìm và trả về độ dài của dãy con Fibonacci dài nhất tồn tại trong dãy arr.

Một dãy con được bắt nguồn từ một dãy khác arr bằng cách xóa bất kỳ số phần tử nào (kể cả không có) khỏi arr, mà không thay đổi thứ tự của các phần tử còn lại.

Ví dụ:nếu đầu vào của hàm là

Đầu vào

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

Đầu ra

const output = 5;

Giải thích đầu ra

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

Sau đây là mã:

Ví dụ

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));