动态编程-部分元素之和

假设我们有一个这样的数字数组-

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

每次减少一个元素，该数组可以像这样分离出来-

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

我们需要编写一个包含一个这样的数组的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 ]