Algorithm: Maximum Sum of Two Non-Overlapping Subarrays

Question

I was working on this algorithm in a leetcode challenge, and I found an interesting approach to the problem. Can anyone explain why, as the first step of this solution, we are adding the value of the previous item to the current?

Example input: [0,6,5,2,2,5,1,9,4], L = 1, M = 2.

Array after summing: [0, 6, 11, 13, 15, 20, 21, 30, 34]

Thanks in advance.

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

I don't understand the coding / algorithm challenge. What two arrays? What are L ad M? I think you left a lot of info out. — Inigo
– Inigo, Commented Apr 18, 2020 at 1:32
When you adding the previous value to current, it will give you the sum of subarray with length i+1. So later when you check subarray sum, if the subarray ending at index i, you know a subarray with length L has sum arr[i] - arr[i-L], so you don't need to iterate again from i-L to i to calculate sum. — Colin
– Colin, Commented Apr 18, 2020 at 1:37
hi, why is the for loop indexed from i = L+M? and can you please explain the for loop as well? — hago
– hago, Commented Jul 19, 2020 at 21:10

Colin · Accepted Answer · 2020-04-18 02:04:31Z

3

When you adding the previous value to current, it will give you sum of subarray with length i+1. So later when you check subarray sum, if the subarray ending at index i, you know a subarray with length L has sum arr[i] - arr[i-L], so you don't need to iterate again from i-L to i to calculate sum.

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

suppose L is length 2 then, later when you iterate array, you know arr[2] - arr[0] is the sum with length 2, same arr[3] - arr[1] is also the subarray sum with length 2. After doing this, you can calculate subarray sum with given length in O(1) time.

Without this step or any memorization, when you calculate non overlap subarray sum for length L and M, each time you will need to take O(L+M) time which is inefficient.

edited Apr 18, 2020 at 2:04

answered Apr 18, 2020 at 1:53

Colin

1,2158 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Algorithm: Maximum Sum of Two Non-Overlapping Subarrays

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related