JavaScriptで配列内の最長フィボナッチ部分列を見つける方法

フィボナッチ数列とは

数列 X_1, X_2, ..., X_n がフィボナッチ数列であるとは、以下の条件を満たすことを指します。

• n >= 3 である

• すべての i + 2 <= n に対して、X_i + X_{i+1} = X_{i+2} が成り立つ

つまり、隣り合う2項の和が常に次の項になる数列のことです。

問題の概要

数値の配列 arr を第1引数(唯一の引数)として受け取り、配列 arr 内に存在する最長のフィボナッチ部分列の長さを見つけて返すJavaScript関数を作成する必要があります。

ここでいう「部分列」とは、元の配列 arr から任意の個数の要素(0個でも構いません)を削除することで得られる列であり、残った要素の相対的な順序は変更されません。

入力例

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

出力例

const output = 5;

出力の解説

この場合、最も長いフィボナッチ部分列は [3, 11, 14, 25, 39] となるため、答えは 5 になります。

実際に確認すると、3 + 11 = 14、11 + 14 = 25、14 + 25 = 39 と、隣接する2項の和が次の項として現れており、フィボナッチ数列の条件を満たしています。

解決策：動的計画法(DP)によるアプローチ

この問題は、ハッシュマップと動的計画法を組み合わせることで効率的に解けます。基本的な考え方は以下の通りです。

• 各値が配列のどのインデックスに位置するかを記録したマップを作成する
• memo[i][j] には、「arr[i] と arr[j] を末尾の2要素とするフィボナッチ部分列の長さ」を格納する
• 各ペア (i, j) に対して、差 b - a の値が配列内に存在し、かつそのインデックスが i より前であれば、部分列を延長できる

以下が実際のコードです。

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

コードの解説

処理の流れを順番に見ていきましょう。

1. マップの作成: reduce を使って、「値 → インデックス」の対応を持つオブジェクト map を生成します。これにより、任意の値が配列内のどこにあるかを O(1) で調べられるようになります。
2. メモテーブルの初期化: 二次元配列 memo を用意し、すべての要素を 0 で初期化します。
3. ペアごとの判定: すべてのインデックスの組み合わせ (i, j) について、arr[j] - arr[i] の値がマップに存在し、そのインデックスが i 未満であれば、3つの項でフィボナッチ関係が成立するため memo[i][j] を更新します。
4. 結果の返却: フィボナッチ部分列が見つかった場合は、最大長に初期の2要素分(+2)を加えた値を返し、1つも見つからなければ 0 を返します。

このアルゴリズムの時間計算量は O(n²)、空間計算量も O(n²) であり、全探索(指数時間)に比べて大幅に効率化されています。

実行結果

5