Problem: Maximum Sum Subarray of Size K

Problem Statement

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

Approach: Fixed-Size Sliding Window

Instead of recalculating the sum for every subarray ($O(n \times k)$), we use a sliding window to update the sum in $O(1)$ time.

1. Initialize: Calculate the sum of the first k elements.
2. Slide: Move the window forward one element at a time.
3. Update:
   • Add the new element entering the window.
   • Subtract the element leaving the window.
   • Update maxSum if the new sum is larger.

Java Implementation

public int findMaxSumSubarray(int[] arr, int k) {
    int windowSum = 0;
    int maxSum = 0;
    int windowStart = 0;

    for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
        windowSum += arr[windowEnd]; // Add the next element

        // Slide the window, we don't need to slide until we've hit window size 'k'
        if (windowEnd >= k - 1) {
            maxSum = Math.max(maxSum, windowSum);
            windowSum -= arr[windowStart]; // Subtract the element going out
            windowStart++; // Slide the window ahead
        }
    }
    return maxSum;
}

Complexity Discussion

• Time Complexity: $O(n)$.
• Space Complexity: $O(1)$.