Recently I've come up with this problem:
You are given an array $$$a_1, a_2, \dots, a_n$$$ of positive integers.
You need to find $$$l$$$, $$$r$$$ such that $$$\frac{\prod_{i=l}^{r} a_i}{r-l+1}$$$ is maximum over all possible $$$l,r$$$ $$$(l \leq r)$$$.
Is it possible to solve this faster than $$$O(n^2)$$$? This problem looks like something well-known, but I am not sure.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 161 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
Auto comment: topic has been updated by Skeef79 (previous revision, new revision, compare).
Let yi = sum of ai up to index i, xi = i. Then for some (l, r) the value of the abovementioned formula is (yr — yl) / (xr — xl) , So i think you can go from left to right and maintain a lower hull of the (xi, yi)'s or something along those lines.
Edit : I wrote the answer for the sum, because you have used sum in the above formula, do you mean product or sum ?
Whoops, i mean product... Sorry, my bad
No worries. Okay i am going to forget about the product of numbers being possibly to large to fit into any data type in the following section. Let yi = product of ai up to index i. Product on range = yr/yl * 1/(r — l) reverse the formula and instead minimize : (yl*r — yl*l)/(yr) . Now look at; yr as a constant, yl as your "k", and -yl*l as your "b", and at "r" as your "x", so you have a line of form ( k*x + b ) / constant . So you can solve it again with lines, maintaining upper/lower envelope as you iterate from left to right.
Nice solution if numbers are small.
Bin search on answer
Auto comment: topic has been updated by Skeef79 (previous revision, new revision, compare).
Denote $$$P = \prod_{i=1}^N a_i$$$. One obvious answer is $$$\frac{P}{N}$$$. Now, this answer might not be optimal, and one may give up on some values $$$a_i$$$ for the sake of a lower numerator.
However, note that the product of the numbers that you give up must never exceed $$$N$$$. Also, note that it's never optimal to have $$$a_l = 1$$$ or $$$a_r = 1$$$. These two observations imply that there are at most $$$\log^2 N$$$ "interesting" pairs $$$(l, r)$$$.
For each such pair you have to compare $$$\frac{1}{r-l+1} \prod_{i=l}^r a_i$$$. However, these numbers might be really big. Instead, note that that product above equals, in fact, $$$\frac{P}{(r-l+1)p}$$$, where $$$p$$$ is the product of the numbers that you're not including in your range (and should be smaller than $$$N$$$), and $$$P$$$ is the product of all numbers.
Then, you can just compare $$$(r-l+1)p$$$ instead of those huge numbers.
Why cannot we work on logarithm of numbers, and convert it to classic maximum average of subarray task.
https://mirror.codeforces.com/blog/entry/21103
Correct me if I am wrong,let's say $$$f(l,r) = \sum_{i=l}^r log(a_i)$$$ and $$$g(l,r) = \prod_{i=l}^r a_i $$$
So , maximize $$$g(l,r) / (r-l+1) $$$ is equivalent to maximize $$$f(l,r) / (r-l+1)$$$ as $$$r-l+1$$$ is just dividing factor.
no you should minimize f(l,r) — log(r-l+1), not equivslent at all
The problem should ask for the subarray's endpoints which maximize the value.
Fixed
Thank you! Awesome solution.
Auto comment: topic has been updated by Skeef79 (previous revision, new revision, compare).
UPD: Wrong solution