I simply calculate the prefix sums while traversing the array. Here's the logic:
- Start with the range being from i,j = [0,K-1]. Then iterate over remaining elements.
- For every next element, j, we add, we have a choice - we can use the full range [i,j] or discard the range [i:j-k] and keep [j-k+1:j] (i.e keep the latest K elements). Choose the range with the higher average (use prefix sum to do this in O(1)).
- Keep track of the max average at every step
- Return the max avg at the end
class Solution(object): def findMaxAverage(self, nums, k): prefix =  for i in range(k): prefix.append(float(prefix[-1] + nums[i])) mavg = prefix[-1]/k lbound = -1 for i in range(k,len(nums)): prefix.append(prefix[-1] + nums[i]) cavg = (prefix[i+1] - prefix[lbound+1])/(i-lbound) altavg = (prefix[i+1] - prefix[i-k+1])/k if altavg > cavg: lbound = i-k cavg = altavg mavg = max(mavg, cavg) return mavg
Please let me know if you see any issues here.