使用 JavaScript 在数组中查找斐波那契数列

Z时代
2024-01-10
分类：综合

斐波那契数列：

序列 X_1, X_2, ..., X_n 是斐波那契数列，如果：

n >= 3
X_i + X_{i+1} = X_{i+2} 对于所有 i + 2 <= n

问题

我们需要编写一个 JavaScript 函数，它接受一个数字数组 arr 作为第一个也是唯一的参数。我们的函数应该找到并返回数组 arr 中存在的最长斐波那契子序列的长度。

通过从 arr 中删除任意数量的元素（包括无），而不改变其余元素的顺序，从另一个序列 arr 派生出一个子序列。

例如，如果函数的输入是

输入

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

输出

const output = 5;

输出说明

因为最长的斐波那契子序列是 [3, 11, 14, 25, 39]

以下是代码：

示例

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