Алгоритм: максимальная сумма двух неперекрывающихся подмассивов

Question

Я работал над этим алгоритмом в вызове leetcode, и я нашел интересный подход к проблеме. Может кто-нибудь объяснить, почему в качестве первого шага этого решения мы добавляем значение предыдущего элемента к текущему?

Пример ввода: [0,6,5,2,2,5,1,9,4], L = 1, M = 2 .

Массив после суммирования: [0, 6, 11, 13, 15, 20, 21, 30, 34]

Заранее спасибо.

const maxSumTwoNoOverlap = (arr, L, M) => {
    let len = arr.length;
    for (let i = 1; i < len; i++) {
        arr[i] += arr[i - 1];
    }

    let LMax = arr[L - 1], MMax = arr[M-1];
    let res = arr[M + L - 1];

    console.log('LMax', LMax);
    console.log('MMax', MMax);

    for (let i = M + L ; i< len ; i++) {
        // update LMax to i - M; 
        LMax = Math.max(LMax, arr[i - M] - arr[i - M - L]);
        MMax = Math.max(MMax, arr[i - L] - arr[i - M - L]);
        res = Math.max(res,
            LMax + arr[i] - arr[i - M],
            MMax + arr[i] - arr[i - L]
        )
    }

    return res;
};

Answer 1

Когда вы добавляете предыдущее значение к текущему, оно даст вам сумму подмассива длиной i + 1. Поэтому позже, когда вы проверяете сумму подмассива, если подмассив заканчивается на индекс i, вы знаете, что подмассив с длиной L имеет сумму arr [i] - arr [iL] , поэтому вам не нужно повторять итерацию снова от iL до i для вычисления суммы.

    0 arr[0]
    1 arr[0] + arr[1]
    2 arr[0] + arr[1] + arr[2]
    3 arr[0] + arr[1] + arr[2] + arr[3]
    ...

предположим, что L - это длина 2, а затем, когда вы перебираете массив, вы знаете, arr [2] - arr [0] - это сумма с длиной 2, то же самое arr [3] - arr [1] также является суммой подмассива с длиной 2. После этого вы можете вычислить сумму подмассива с заданной длиной в O (1) время

Без этого шага или какого-либо запоминания, когда вы вычисляете сумму неперекрывающихся подмассивов для длины L и M, каждый раз вам понадобится O (L + M) время, которое неэффективно.