Maximum Average Subarray of Size K

You are given an array of n integers and an integer k. Find the contiguous subarray of exactly k elements whose average value is the largest, and print that maximum average. The average of a window is its sum divided by k.

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 floating point number: the maximum average, formatted with exactly 5 digits after the decimal point.

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

This is a great example of a problem that LOOKS different (asking for an average) but is mathematically identical to a problem you may already know how to solve (maximum sum) - always check if a fixed divisor or scaling factor lets you reduce to a simpler, already-known problem.

Find the k-length contiguous subarray with the highest average value. Brute force: Compute the sum (and then average) of every window directly by summing all k elements each time - this costs O(n*k), unnecessary once you recognize this reduces to the maximum-sum sliding window problem. Optimised: Since AVERAGE = SUM / k and k is fixed across every window being compared, maximizing the average is mathematically IDENTICAL to maximizing the sum - there's no need to track averages directly at all during the sliding process; just find the maximum sum and divide once at the end.

1. Recognize that since k is FIXED across every window, the window with the maximum AVERAGE is the SAME window with the maximum SUM. 2. Reuse the fixed-size sliding window technique (add incoming, subtract outgoing) to find the maximum sum in O(n). 3. Divide that maximum sum by k at the very end, and print with the required decimal precision.

Time: O(n) - the same fixed-size sliding window sum technique, with one final division. Space: O(1) - a running sum and a running maximum.

Handle k = 1 (the maximum average equals the maximum element) and k = n (the average of the whole array). Averages may be negative when every element is negative.

Be ready to point out immediately that this problem REDUCES to 'maximum sum subarray of size k' - recognizing this reduction instantly (rather than re-deriving a separate average-tracking technique) is exactly the kind of pattern recognition that saves time under interview pressure.