Quy hoạch động - Tổng phần tử phần tử trong JavaScript

Giả sử chúng ta có mảng số như sau:

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

Lấy bớt một phần tử mỗi lần, mảng có thể tách ra như:

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

Cần viết hàm nhận mảng như vậy. Hàm tách mảng theo cách trên. Hàm xây dựng mảng chứa tổng tương ứng của các phần này và trả về mảng đó.

Đầu ra cho mảng này:

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

Sử dụng Quy hoạch động. Tính tổng mảng hoàn chỉnh O(n) - thành phần tử đầu tiên. Sau đó lặp lại, trừ dần phần tử tương ứng để lấy các phần tử mảng kết quả. Cách này giải quyết 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));

Kết quả

Điều này sẽ tạo ra đầu ra sau:

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