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.

• +10

 » 4 years ago, # |   +51 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 →   +3 Your idea seems excellent :) thank you :)
•  » » 4 years ago, # ^ |   +3 Can it be done in O(n) complexity?
•  » » » 4 years ago, # ^ |   0 there isn't any way that i know of ! if anybody knows anything please say ;D
•  » » » 4 years ago, # ^ |   +15 It's possible: http://www.cs.cornell.edu/~chung/download/density.pdf
•  » » » » 4 years ago, # ^ |   0 Tnx :) But the article seems difficult to me :( If u know the algorithm can you please explain :/
•  » » » » 4 years ago, # ^ |   0 It would be nice if u can write the crux of article here .That would be helpfull .
•  » » » » » 4 years ago, # ^ |   +2 I'll write a blog post about this topic when I have time for it.
•  » » » » » » 4 years ago, # ^ |   0 The link is not working. Do you have any other references?
•  » » » » » » » 4 years ago, # ^ |   +9
•  » » » » » » » » 4 years ago, # ^ |   0 That question is not even based on this!
•  » » » » » » » » » 4 years ago, # ^ |   0 So you participated in the contest but this wasn't based on it? — http://store.picbg.net/pubpic/B3/4C/eb16def031d2b34c.png
•  » » » » » » » » » 4 years ago, # ^ |   0 Yes I did participate. And yes it is not based on the sum.
•  » » » » » » » 4 years ago, # ^ |   +2 Another link: http://arxiv.org/abs/cs/0311020
•  » » » » » » » » 4 years ago, # ^ |   +8 Thank you!
 » 12 months ago, # |   -31