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

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

ลำดับ X_1, X_2, ..., X_n คือฟีโบนักชีถ้า:

น>=3
X_i + X_{i+1} =X_{i+2} สำหรับ i + 2 ทั้งหมด <=n

ปัญหา

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของตัวเลข arr เป็นอาร์กิวเมนต์แรกและอาร์กิวเมนต์เดียว ฟังก์ชันของเราควรค้นหาและส่งกลับความยาวของลำดับย่อย Fibonacci ที่ยาวที่สุดที่มีอยู่ในอาร์เรย์ 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));