### Hand1e's blog

By Hand1e, history, 3 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
•  » » 3 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
•  » » » It's possible: http://www.cs.cornell.edu/~chung/download/density.pdf
•  » » » » Tnx :) But the article seems difficult to me :( If u know the algorithm can you please explain :/
•  » » » » It would be nice if u can write the crux of article here .That would be helpfull .
•  » » » » » I'll write a blog post about this topic when I have time for it.
•  » » » » » » The link is not working. Do you have any other references?
•  » » » » » » »
•  » » » » » » » » That question is not even based on this!
•  » » » » » » » » » So you participated in the contest but this wasn't based on it? — http://store.picbg.net/pubpic/B3/4C/eb16def031d2b34c.png
•  » » » » » » » » » Yes I did participate. And yes it is not based on the sum.
•  » » » » » » » Another link: http://arxiv.org/abs/cs/0311020
•  » » » » » » » » Thank you!
 »