Lập trình động - Tổng một phần của các phần tử JavaScript

Giả sử, chúng ta có một mảng các số như thế này -

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

Mỗi lần bớt đi một phần tử, mảng này có thể được tách ra như thế này -

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

Chúng tôi được yêu cầu viết một hàm JavaScript có trong một mảng như vậy. Hàm phải tách mảng theo cách tương tự được mô tả ở trên.

Sau đó, hàm sẽ tạo một mảng chứa các tổng tương ứng của các phần này và trả về mảng đó.

Do đó, đối với mảng này, đầu ra sẽ giống như -

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

Chúng tôi sẽ sử dụng Lập trình động để giải quyết vấn đề này. Đầu tiên chúng ta sẽ tính toán tổng của mảng hoàn chỉnh trong thời gian O (n), cuối cùng nó sẽ trở thành phần tử đầu tiên của mảng. Bằng cách này, chúng ta có thể giải quyết vấn đề này trong O (n) thời gian và O (1) không gian.

Ví dụ

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));

Đầu ra

Điều này sẽ tạo ra kết quả sau -

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