Return to Revisions

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, any solid cut needs to have an odd length: $$ \operatorname{SolidCut}(a, b) \Rightarrow b - a = 2k + 1 \wedge k > 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.