Max Sum Subarray of size k

Problem Link

Max Sum Subarray of size K – GFG

Problem Statement

You are given an integer array arr[] and an integer k. Your task is to find the maximum sum of any contiguous subarray of size k.

A subarray is a contiguous part of an array, and you are restricted to consider only those subarrays whose size is exactly k.

Examples

• Input: arr = [100, 200, 300, 400], k = 2
  Output: 700
  Explanation: Subarray [300, 400] has the maximum sum.

• Input: arr = [100, 200, 300, 400], k = 4
  Output: 1000
  Explanation: Entire array is the only subarray of size 4.

• Input: arr = [100, 200, 300, 400], k = 1
  Output: 400
  Explanation: Single element 400 is the maximum.

Constraints

• 1 <= arr.length <= 10^6

• 1 <= arr[i] <= 10^6

• 1 <= k <= arr.length

Intuition

The goal is to find the maximum sum of all subarrays of size k in an efficient way.

A naive approach would be to iterate over all possible subarrays of size k and compute their sums individually. However, this takes O(n * k) time, which is inefficient for large arrays.

This is a classic case where the Fixed Size Sliding Window Technique is ideal.

Approach

1. First compute the sum of the first k elements. This forms your initial window.

2. Then slide the window one element at a time:

   • Subtract the element that is going out of the window (i.e., arr[i - k])

   • Add the new element that is coming into the window (i.e., arr[i])

   • Update the maximum sum accordingly

3. Return the maximum sum found.

This approach reduces time complexity to O(n).

Java Code

class Solution {
    public int maximumSumSubarray(int[] arr, int k) {
        int sum = 0;

        // Compute sum of first window
        for(int i = 0; i < k; i++){
            sum += arr[i];
        }

        int maxSum = sum;

        // Slide the window across the array
        for(int i = k; i < arr.length; i++){
            sum -= arr[i - k];     // remove first element of previous window
            sum += arr[i];         // add new element of current window
            maxSum = Math.max(maxSum, sum);  // update max
        }

        return maxSum;
    }
}

Time and Space Complexity

• Time Complexity: O(n)
  Only a single traversal of the array is done. Each element is added and removed at most once.

• Space Complexity: O(1)
  Only a few integer variables are used for tracking the sum and max.

Dry Run

Input:

arr = [100, 200, 300, 400], k = 2

Steps:

• Initial window sum = 100 + 200 = 300, maxSum = 300

• Slide window:

  • Remove 100, add 300 → sum = 300 + 300 - 100 = 500, maxSum = 500

  • Remove 200, add 400 → sum = 500 + 400 - 200 = 700, maxSum = 700

• End of loop

Output: 700

Conclusion

This problem is a textbook application of the Fixed Size Sliding Window technique. The sliding mechanism ensures that we re-use previous computations efficiently, making it ideal for real-time or memory-constrained environments.

The same logic can be extended to more advanced variants:

• Maximum sum subarray with at most k elements

• Minimum sum subarray of size k

• Maximum average subarray of size k

This foundational pattern is essential for mastering window-based problems.