Algorithm for subarray of length k with maximum sum

Question

I was asked this question in an interview:

Find the maximum subarray of elements with length of k

For example:

• Input: [1,-5,4,3,6,8,2,4], k = 3
• Output: [3,6,8]

I thought to just take all possible slices of the input array and calculate the sum of each, and then keep the greatest sum. It turns out this is not efficient.

How can this be done more efficiently?

Answer 1

The idea is that you slide a window over the array.

Use two indices in the array: one at 0, one at k. Calculate the sum of the values in that range (up to and including the value at k-1). Then move the window and adapt the sum. Remember which was the greatest sum and its location.

Here in JavaScript implementation:

function greatestSum(arr, k) {
    const n = arr.length;
    // Initialise 
    let sum = 0;
    for (let i = 0; i < k; i++) {
        sum += arr[i];
    }
    let maxSum = sum;
    let maxStart = 0;
    // Look for all alternative subarrays
    for (let i = 0; i < n - k; i++) {
        sum = sum - arr[i] + arr[i + k]; // Move the window
        if (sum > maxSum) { // Improvement found
            maxSum = sum;
            maxStart = i + 1;
        }
    }
    // Extract the slice that has the maximum sum
    return arr.slice(maxStart, maxStart + k);
}

const arr = [1,-5,4,3,6,8,2,4]
const k = 3;
const output = greatestSum(arr, k);
console.log(output); // [3,6,8]