動的計画法-要素の部分和JavaScript

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

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

毎回1つの要素を減らすと、この配列は次のように分離できます-

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

そのような配列を1つ取り込むJavaScript関数を作成する必要があります。関数は、上記と同じ方法で配列を分離する必要があります。

次に、関数はこれらの部分のそれぞれの合計を含む配列を作成し、その配列を返す必要があります。

したがって、この配列の場合、出力は-

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

この問題を解決するために動的計画法を使用します。最初に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 ]