Maximum Average Subarray I — Editorial

Opening the reading…

Intuitionwhy comparing sums is enough

Every candidate has exactly k elements, so its average is its sum divided by the same positive number k. That means the window with the largest average is exactly the window with the largest sum. The problem therefore becomes: inspect every contiguous block of length k and keep the greatest sum.

Adjacent windows overlap in k - 1 positions. When the window moves one step right, only two values change: the old leftmost value leaves and the new rightmost value enters. Reusing the previous sum gives the next sum in constant time, and dividing only the final maximum by k avoids unnecessary floating-point work.

One update moves a fixed-size window by removing one value and adding one value.

Approachone initial sum, then one update per shift

Sum the first k elements and store that value as the current window sum, because every later window will be derived from this complete starting window.

Set maxSum to the first window sum instead of to zero, because an array containing only negative values must still produce a negative maximum.

For each index i from k through n - 1, add nums[i] and subtract nums[i - k], because those are exactly the entering and leaving values when the window shifts right.

Compare the updated sum with maxSum and retain the larger one, because each shift produces one new candidate window that must be considered.

Return maxSum divided by k as a double, because all candidate windows have the same length and the final result is an average rather than a sum.

Complexitythe overlap makes the scan linear

MEASURE	BOUND	WHY
Time	O(n)	The first window uses k additions, and each of the remaining n - k windows uses one addition, one subtraction, and one comparison. Each array element enters and leaves the running window at most once, so no window is rescanned.
Space	O(1) extra	Only the current sum, the best sum, and loop variables are stored. The returned average is one scalar of required output, so it is excluded from working space; the bound stays O(1) for every input shape.

Here n is the array length and k is the fixed window length.

Annotated solutionC++ · fixed-size sliding window · complete judge-ready implementation

CPPCompute the first window sum, update it as the window slides, and divide the best sum by k.

#include <vector>

using namespace std;

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int sum = 0;
        for (int i = 0; i < k; ++i) {
            sum += nums[i];
        }

        int maxSum = sum;
        for (int i = k; i < static_cast<int>(nums.size()); ++i) {
            sum += nums[i] - nums[i - k];
            if (sum > maxSum) {
                maxSum = sum;
            }
        }

        return static_cast<double>(maxSum) / k;
    }
};

The initialization of maxSum is part of the algorithm, not bookkeeping. The first window is a valid candidate before the loop begins, so it supplies a real baseline. This matters when every value is negative: starting maxSum at zero would make an impossible empty choice look better than every legal window.

The cast in the return statement controls the division type. Without converting maxSum to double first, integer division would discard the fractional part before the result is returned. Casting only after division cannot restore that lost precision.