Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### Hand1e's blog

By Hand1e, history, 4 years ago, , Suppose you are given an array of n integers and an integer k (n<= 10^5, 1<=k<=n). How to find the sub-array(contiguous) with maximum average whose length is more than k. Comments (16)
 » first we do a binary search on the average and let it be x we decrease x from all of the array elements and if there exists a sub array with lengh more than k whose sum is more than zero then we can say that we have such a sub array whose average is more than x other wise we can say that there doesnt exist any such sub array how to find out if there is a sub array whose sum is more than zero and its length is more than k? we can say that a sub array [l, r) equals sum[1, r) — sum[1, l) so if we get the partial sums and fix the r of the sub array we just need an l which sum[1, r) >= sum[1, l) and l <= r — k this can be done with partial minimum of the partial sums
•  » » 4 years ago, # ^ | ← Rev. 2 →   Your idea seems excellent :) thank you :)
•  » » Can it be done in O(n) complexity?
•  » » » there isn't any way that i know of ! if anybody knows anything please say ;D