I have a finite sequence of positive real numbers $p\_1,\dots, p\_n$ and I am looking for a monotonically ascending sequence of indices $z\_1,\dots, z\_k$ that starts with $z\_1 = 1$ and ends with $z\_k = n$ in order to maximize the following product over all $k,z\_1,\dots, z\_k$:
$$
\prod\_{i = 1}^{k - 1} \frac{p\_{z\_i} + p\_{z\_{i + 1}}}{2 \sqrt{p\_{z\_i} p\_{z\_{i + 1}}}}.
$$
How do I approach this optimization problem? Ideally, I am looking for an efficient algorithm that can find the optimal sequence $(z\_i)$ given any input sequence $(p\_i)$, typically containing millions of elements.



Optimal Talmudic Zigzag
It is easy to see that the optimal subsequence needs to be a zigzag. Then, assuming the $(p\_i)$ sequence is replaced with its longest zigzag subsequence, one can define *cuts* as intervals that do not increase the product that needs to be maximized:
$$
\operatorname{Cut}(a, b) \Leftrightarrow \prod\_{i = a}^{b - 1} \frac{p\_i + p\_{i + 1}}{2 \sqrt{p\_i p\_{i + 1}}} \le \frac{p\_a + p\_b}{2 \sqrt{p\_a p\_b}}.
$$
Also, let an interval be called *solid* when it does not include any shorter cuts:
$$
\operatorname{Solid}(a, b) \Leftrightarrow \nexists i,j \in [a, b]: \operatorname{Cut}(i, j) \wedge j - i < b - a.
$$
Finally, it will be particularly useful to distinguish *solid cuts*:
$$
\operatorname{SolidCut}(a, b) \Leftrightarrow \operatorname{Solid}(a, b) \wedge \operatorname{Cut}(a, b).
$$
Due to the properties discussed in [this paper](https://ssrn.com/abstract=3166840), any solid cut needs to have an odd length:
$$
\operatorname{SolidCut}(a, b) \Rightarrow b - a = 2k + 1 \wedge k \ge 1,
$$
and any chain of overlapping solid cuts is also a cut. Thus the optimal subsequence cannot include any elements that are within solid cuts. However, after removing all elements that are within solid cuts, the resulting sequence can have some new solid cuts, so the process needs to be repeated until no cuts remain, reaching the optimal subsequence.


