การหาลำดับฟีโบนัชชีในอาร์เรย์ด้วย JavaScript

ลำดับฟีโบนัชชี

ลำดับ X_1, X_2, ..., X_n เป็นฟีโบนัชชี หาก:

• n >= 3
• X_i + X_{i+1} = X_{i+2} สำหรับทุก i + 2 <= n

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของตัวเลข arr เป็นอาร์กิวเมนต์เดียว ฟังก์ชันควรหาและคืนค่าความยาวของลำดับฟีโบนัชชีย่อย (subsequence) ที่ยาวที่สุดที่มีอยู่ในอาร์เรย์ arr

ลำดับย่อย (subsequence) มาจากลำดับอื่น 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));

ผลลัพธ์

5