Sliding Window: Maximum Contiguous Subarray

An algorithm problem solved using the sliding window approach

Hello!

As promised in the last newsletter, we will be covering an algorithm question this week. We covered this problem in our initial release for Two Pointer Algorithms. For those who haven’t seen that, here is the link to it.

In that newsletter, we considered an example where I promised you candies, but you could only take from consecutive bags (bags that are next to each other). In order to get the most candy, we agreed that keeping a static distance between me and my friend while we checked the bags was a good approach. Today, we see a practical implementation of that algorithm.

Maximum Contiguous Subarray

The maximum contiguous subarray problem states that given an array of integer, arr, and an integer K, find the maximum sum of the contiguous subarray of length K.

Contiguous here means elements or items in the array that are next to each other. The size of the sub array is dictated by the value K.

Solution

This is a classic sliding window algorithm question. Other variations of this question can ask for the average of the maximum contiguous subarray or the minimum contiguous subarray. Using a sliding window, we can get the sum of the subarray of length K, then slide the window left to right, removing the element at the beginning of the window and adding the element to the right of the window. K serves as the length of our window.

const maxSubArray = (arr, k) => {

   let sum = 0, maxSum=0

   let windowStart = 0

   for(let windowEnd = 0; windowEnd<arr.length; windowEnd++) {

//sum values till we get to size k

       if(windowEnd < k) {

           sum += arr[windowEnd]

       }

//if we are at or above the k limit, slide right

       if(windowEnd >= k) {

           maxSum = Math.max(maxSum, sum)

           sum -= arr[windowStart]

           sum += arr[windowEnd]

           windowStart++

       }

   }

   return Math.max(sum, maxSum)

}

Our solution may not seem intuitive at first, but a quick look at it explains why we consider the sliding window a good approach.

Looping through the length of our array, we first sum up the values of the elements up until index k. Once we are at k, we know we’ve reached the size of our window. We then proceed to implement the sliding logic. We set our new maxSum by taking the maximum of the sum and the current maximum sum. The final step is to slide our window by subtracting the element at the beginning of the window, and adding the element at the end of our window. By incrementing the windowStart by 1, we move the start of the window upwards, thus maintaining the original length of the sub array (k).

Runtime

The sliding window approach solves the maximum subarray problem in O(n). If you are not aware of how we got O(n), please read my previous release on Big O’ Notation.

In summary, we are only looping through the length of the array once.

Conclusion

This is a short one, but I hope you enjoyed it. The key to solving algorithm questions is in knowing what algorithm and/or data structure to apply to the given problem. With this release, I hoped to make the kind of problems you’d be able to solve with sliding window a little clearer. Feel free to leave comments, questions, or suggestions.

See you next week!