동적 프로그래밍 - JavaScript 요소의 일부 합계

다음과 같은 숫자 배열이 있다고 가정해 보겠습니다. -

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 ]