【JavaScript】動的計画法で配列の部分和を効率的に求める方法

問題の概要

次のような数値の配列があるとします。

const arr = [1, 2, 3, 4, 5];

この配列は、先頭から1つずつ要素を減らしながら、以下のように分割できます。

[1, 2, 3, 4, 5]
[2, 3, 4, 5]
[3, 4, 5]
[4, 5]
[5]
[]

今回作成するのは、このような配列を受け取り、上記の方法で配列を分割していくJavaScript関数です。さらに、分割された各部分ごとの合計値を要素として持つ新しい配列を構築し、それを返す必要があります。

したがって、この配列の場合、期待される出力は次のようになります。

const output = [15, 14, 12, 9, 5, 0];

動的計画法によるアプローチ

この問題は動的計画法(Dynamic Programming)を使うことで効率的に解けます。手順は以下の通りです。

1. まず、配列全体の合計をO(n)の時間計算量で計算します。これが結果配列の最初の要素になります。
2. 次にもう一度ループを回し、対応する要素を順番に合計値から引いていくことで、出力配列の残りの要素を求めていきます。

毎回部分配列の合計をゼロから再計算するとO(n²)の計算量が必要になりますが、直前の合計値を再利用することで、時間計算量O(n)・空間計算量O(1)という非常に効率的な実装が可能になります。

実装例

const arr = [1, 2, 3, 4, 5];

// 配列全体の合計を求めるヘルパー関数
const sumArray = (arr = []) => arr.reduce((a, b) => a + b, 0);

const partialSum = (arr = []) => {
   let sum = sumArray(arr);
   const res = [sum];
   for(let i = 0; i < arr.length; i++){
      const el = arr[i];
      sum -= el;
      res.push(sum);
   }
   return res;
};

console.log(partialSum(arr));

実行結果

このコードを実行すると、コンソールには次の出力が表示されます。

[ 15, 14, 12, 9, 5, 0 ]

コードの解説

処理の流れを簡単に整理してみましょう。

• sumArray: reduceメソッドを使い、配列全体の合計(この例では15)を一度だけ計算します。
• partialSum: 合計値15を出発点として、ループ内で配列の各要素(1, 2, 3, 4, 5)を順に引きながら、その都度結果をres配列へ追加していきます。
• その結果、「15 → 14 → 12 → 9 → 5 → 0」という部分和の並びを持つ配列が完成します。

このように、すでに計算済みの合計をうまく活用するのが動的計画法の基本的な考え方であり、同じ計算を繰り返さないことで処理を大幅に高速化できます。