Maximum Sum Subarray of Size K

Problem Statement: Maximum Sum Subarray of Size K

Given an array of positive integers, and a positive number k, find the maximum sum of any contiguous subarray of size k.

Example 1

Input: [3, 5, 2, 1, 7], k=2 
Output: 8
Explanation: Subarray with maximum sum is [1, 7].

Example 2

Input: a[] = {4, 2, 3, 5, 1, 2}, k = 3
Output: 10
Explanation: Subarray with maximum sum is [2, 3, 5]

Solution Approach

Brute force

A naive brute force approach will be to calculate the sum of all subarrays of size k of the given array to find the maximum sum.

This will require two for loops. You can start a loop that runs for every index of the array and then for each index you start another loop to add the next k elements. This way, you will be able to calculate the sum of all k-sized subarrays and then return the maximum of all the sums.

import java.util.Scanner;

class MaxSumSubarrayOfSizeK {
    public static int findMaxSumSubarrayOfSizeKBruteForce(int[] a, int k) {
        int maxSum = 0, subarraySum;
        for (int i = 0; i <= a.length-k; i++) {
            subarraySum = 0;
            for (int j = i; j < i+k; j++) {
                subarraySum += a[j];
            }
            maxSum = Math.max(maxSum, subarraySum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int k = keyboard.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = keyboard.nextInt();
        }

        keyboard.close();

        System.out.printf("Max sum subarray of size %d = %d%n", k, findMaxSumSubarrayOfSizeKBruteForce(a, k));
    }
}

The time complexity of the above algorithm is O(n*k), where n is the number of elements in the array, and k is the size of the subarray.

Sliding Window

If you closely observe the way we calculate the sum of subarrays in the brute force approach, you will realize that we’re doing repetitive work while calculating the sum. Let’s look at the following example:

Input: a[] = {4, 2, 3, 5, 1, 2}, k = 3

In the brute force approach, we first calculate the sum of the subarray {4, 2, 3}, then we move to the next subarray and calculate the sum of {2, 3, 5}. Notice that there is an overlap between both the subarrays:

4 2 3
  2 3 5

So, we’re calculating the sum of the overlapping part ({2, 3}) twice. Can we reuse the sum of the overlapping subarray?

Yes! And the approach I am discussing here does exactly that. It is called the Sliding window approach. In this approach, we will calculate the sum of a subarray by utilizing the sum of the previous subarray.

The idea is to consider each subarray as a sliding window of size k. Start with calculating the sum of the first window (first subarray of size k). Now, To calculate the sum of the next subarray, we need to slide the window forward by one element. When we slide the window, we need to do two things to calculate the sum of the new window:

• Subtract the element going out of the sliding window.
• Add the new element getting included in the sliding window.

Here is how this approach applies to the example we were discussing above:

4 2 3
  2 3 5

Sum of the first window (first subarray of size 3) = 9

Sum of the next window (next subarray of size 3) 
  = Sum of the previous window - (Element going out of the window) + (Element getting included in the window)
  = 9 - 4 + 5 = 10

Here is the complete algorithm explained step by step:

• Initialize two variables windowStart and windowEnd both set to zero, i.e., both pointing to the first element of the array. So the initial window size is 1.
• Initialize another variable windowSum = 0 that stores the sum of the current window (current subarray). And a variable maxSum = Integer.MIN_VALUE that keeps track of the maximum sum among all the subarrays of size k.
• Now iterate over the array incrementing windowEnd in each iteration. That means we keep increasing our window forward by one element. In each iteration
  • Add the new element of the array to the window.
  • If the window size (windowEnd-windowStart+1) is equal to k, then we have got the sum of a k-sized subarray in windowSum. Now we need to update maxSum and slide the window to calculate the sum of the next window. To do this:
    • Check if the current windowSum is greater than maxSum. If yes, then update maxSum.
    • Slide the window ahead by subtracting the element at windowStart from windowSum and incrementing windowStart.

Let’s look at the complete code:

import java.util.Scanner;

class MaxSumSubarrayOfSizeK {    
    private static int findSumMaxSubarrayOfSizeK(int[] a, int k) {
        if(k == 0 || a.length == 0) {
            return 0;
        }

        int maxSum = Integer.MIN_VALUE;
        int windowStart = 0;
        int windowSum = 0;

        for(int windowEnd = 0; windowEnd < a.length; windowEnd++) {
            windowSum += a[windowEnd]; // Add the next element to the window
            
            if(windowEnd-windowStart+1 == k) { // When we hit the window size. Update maximum sum, and slide the window
                maxSum = Math.max(maxSum, windowSum);
                windowSum -= a[windowStart]; // Subtract the element going out of the window
                windowStart++; // Slide the window
            }
        }

        return maxSum;
    }
    public static void main(String[] args) {

        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int k = keyboard.nextInt();

        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = keyboard.nextInt();
        }

        keyboard.close();
        
        System.out.printf("Max sum subarray of size %d = %d%n", k, findSumMaxSubarrayOfSizeK(a, k));
    }
}