Maximum Average Subarray I

How it works

All candidate averages share the same denominator k, so maximizing their sum also maximizes the average. Maintain a running sum of exactly k values, replacing the outgoing value with the incoming one at each step.

Steps

1. Sum the first k values and use that as the initial best.
2. Slide by adding the new value and subtracting the one leaving.
3. Return best sum divided by k.

Complexity

• Time: O(n).
• Space: O(1) after summing the initial window without slicing.

Things to watch for

• Initialize from a real window so all-negative inputs work.
• The window length must remain exactly k.
• Use floating-point division for the final average.

class Solution:
  def findMaxAverage(self, nums: list[int], k: int) -> float:
    summ = sum(nums[i] for i in range(k))
    ans = summ

    for i in range(k, len(nums)):
      summ += nums[i] - nums[i - k]
      ans = max(ans, summ)

    return ans / k

class Solution {
 public:
  double findMaxAverage(vector<int>& nums, int k) {
    double sum = accumulate(nums.begin(), nums.begin() + k, 0);
    double ans = sum;

    for (int i = k; i < nums.size(); ++i) {
      sum += nums[i] - nums[i - k];
      ans = max(ans, sum);
    }

    return ans / k;
  }
};