CODEWITHSUNDEEP
javascriptalgorithm
Jose
Jose

Reputation: 5200

Algorithm: Maximum Sum of Two Non-Overlapping Subarrays

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

Upvotes: 1

Views: 1296

Answers (1)

Colin
Colin

Reputation: 1215

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.

Upvotes: 3

Related Questions