Maximum Sum Subarray of Size K

You are given an array of n integers and an integer k. Find the maximum possible sum among all contiguous subarrays that contain exactly k elements. Consider every window of length k as it slides across the array from left to right, and report the largest sum found.

Input: The first line contains two space-separated integers n and k. The second line contains n space-separated integers representing the array. Output: Print a single integer: the maximum sum among all contiguous subarrays of size k.

1 <= k <= n <= 10^5 -10^4 <= arr[i] <= 10^4

The key insight - avoid recomputing a window's full sum after every slide - is the single idea that turns a naive O(n*k) sliding computation into an O(n) one, and it generalizes directly to sums, counts, and other incrementally-maintainable aggregates.

Find the largest possible sum among all contiguous stretches of exactly k elements. Brute force: Recompute the sum of each window from scratch by summing all k elements every time - this costs O(n*k), unnecessary when each slide only changes by one element entering and one leaving. Optimised: Since sliding the window by one position only ADDS one new element and REMOVES one old element, updating the running sum incrementally (rather than re-summing all k elements) turns an O(n*k) approach into a true O(n) single pass.

1. Compute the sum of the FIRST window of size k directly, before sliding anything. 2. To move the window one step right, ADD the new incoming element and SUBTRACT the element that just fell out - never re-sum the whole window from scratch. 3. Track a running maximum as you slide; its final value is the answer.

Time: O(n) - one pass, with O(1) work per slide. Space: O(1) - just a running sum and a running maximum.

Handle k = 1 (the answer is simply the maximum element) and k = n (the answer is the sum of the entire array). The array may contain negative numbers, so the answer itself can be negative.

This is the most foundational fixed-size sliding window problem - be ready to state the 'add incoming, subtract outgoing' update instantly, since it's the building block for every other fixed-size window problem in this category.