A Good Problem

Revision en3, by M_H_M, 2016-03-11 20:57:05

Hello

Consider Array A. For any suffix of A compute the prefix with maximum average.

Example : A => 1 3 2 5 3
Suffix [2, 5) => 2 5 3
Answer => 3.5

Is there a better solution than O(N ^ 2) ??

UPD

IMAN_GH comment :

user:haghani solved the problem and here we have his solution :

sum[i] = a[0] + a[1] + .. + a[i — 1]
for any i consider point (i, sum[i])
if answer for suffix i equals j then (sum[j] — sum[i]) / (j — i) is maximum in all j > i.
it's solution is somthing like upper hull of some points. it solves by using stack with insert points in the hull and updating it.
if we insert points from right to left then answer for suffix i equals to the second point in the upper hull after adding point i.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English M_H_M 2016-03-11 20:58:11 2
en5 English M_H_M 2016-03-11 20:57:51 13
en4 English M_H_M 2016-03-11 20:57:29 24
en3 English M_H_M 2016-03-11 20:57:05 614
en2 English M_H_M 2016-03-06 18:28:54 20
en1 English M_H_M 2016-03-06 18:25:36 220 Initial revision (published)