JavaScriptで隣接しない要素から最大合計の部分集合を求める方法

整数の配列を受け取り、その中から互いに隣接していない要素で構成される部分集合のうち、合計が最大になるものを見つけるJavaScript関数を作成する必要があります。

そして最終的に、その部分集合の合計を計算して返します。

問題の例

例えば、入力配列が以下の場合を考えてみましょう。

const arr = [3, 5, 7, 8, 10];

この場合の出力は 20 になります。これは、隣接しない要素で構成される部分集合として「3, 7, 10」を選んだとき、その合計が 20 となり、これが最大となるためです。

サンプルコード

const arr = [3, 5, 7, 8, 10];
const maxSubsetSum = (arr = []) => {
    let min = -Infinity
    const helper = (arr, ind) => {
        if ( ind < 0 ){
            return min
        };
        let inc = helper(arr, ind-2);
        let notInc = helper(arr, ind-1);
        inc = inc == min ? arr[ind] : Math.max(arr[ind], arr[ind] + inc);
        return Math.max( inc, notInc );
    };
    return helper(arr, arr.length - 1);
};
console.log(maxSubsetSum(arr));

コードの解説

このアルゴリズムは再帰を利用したアプローチです。各インデックスの位置において、次の2つの選択肢を比較します。

• 現在の要素を選ぶ場合：隣接する直前の要素は選べないため、2つ前まで遡って計算した結果に現在の要素を加えた値になります。
• 現在の要素を選ばない場合：1つ前まで遡って計算した結果をそのまま利用します。

この2つの値のうち大きい方を順に採用していくことで、最終的な最大合計が求まります。

なお、この実装は再帰をそのまま使っているため、配列の長さが増えると計算量が指数的に膨らむという弱点があります。実際の開発では、メモ化（キャッシュ）や動的計画法（DP）を組み合わせて処理を効率化するのが一般的です。

実行結果

コンソールには次のように出力されます。

20