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.
Thanks in advance.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
4 | adamant | 160 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
8 | Dominater069 | 154 |
8 | nor | 154 |
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.
Thanks in advance.
Name |
---|
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
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?
Coincidence?
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!