A Good Problem

Revision en6, by M_H_M, 2016-03-11 20:58:11

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

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

### UPD

IMAN_GH's comment :

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 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)