JavaScript में सरणी में फाइबोनैचि अनुक्रम ढूंढना

फाइबोनैचि अनुक्रम:

एक अनुक्रम X₁, X₂, ..., Xₙ फाइबोनैचि है यदि:

• n ≥ 3
• Xᵢ + Xᵢ₊₁ = Xᵢ₊₂ सभी i + 2 ≤ n के लिए

समस्या

हमें एक JavaScript फ़ंक्शन लिखना है जो संख्याओं की एक सरणी, 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));

आउटपुट

5