Given a sorted array of even length $\{a_1, a_2, \ldots, a_{2n}\}$, we need to pair these elements and multiply the sum of each pair. The largest value should be $(a_1 + a_{2n}) \times (a_2 + a_{2n-1}) \cdots$.
Let's consider an easier case. Suppose we have 4 numbers $a<b<c<d$. It's obvious that $(a+d)(b+c)>(a+b)(c+d)$ and $(a+d)(b+c)>(a+c)(b+d)$. How can we generalize this property?
Suppose $a_1$ is paired with some $a_i$, and $a_{2n}$ is paired with some $a_j$. By a single exchange, we could get a better solution. After that, the pair of the smallest & largest element remains the same, and we can use induction here for inner elements.
Sometimes it's just essential to prove pairwise inequalities for sequence optimality.
No comments:
Post a Comment