A Good Problem

Правка en4, от M_H_M, 2016-03-11 20:57:29

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский M_H_M 2016-03-11 20:58:11 2
en5 Английский M_H_M 2016-03-11 20:57:51 13
en4 Английский M_H_M 2016-03-11 20:57:29 24
en3 Английский M_H_M 2016-03-11 20:57:05 614
en2 Английский M_H_M 2016-03-06 18:28:54 20
en1 Английский M_H_M 2016-03-06 18:25:36 220 Initial revision (published)