Hand1e's blog

Sub-array With Maximum Average
By Hand1e, history, 9 years ago, In English

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.

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
9 years ago, # |
  Vote: I like it +51 Vote: I do not like it

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

→ Reply