Автор и разработчик задачи: Гайнуллин Ильдар
Чтобы найти идеальное паросочетание максимального веса, можно воспользоваться следующим жадным алгоритмом:
Выберем элемент наибольшего веса. Заметим, что ребер с весом равным этому элементу должно быть максимальное возможное количество. Поэтому, к ответу нужно добавить $$$a_i \cdot \min{(i, (n + 1 - i))}$$$. После чего, рекурсивно запуститься от большей половины с задачей «найти паросочетание максимального веса размера $$$k$$$ для отрезка вершин».
Из этого алгоритма следует, что для фиксированной длины $$$n$$$, $$$i$$$-й элемент в отсортированном порядке прибавляет к ответу $$$a_i \cdot b_i$$$, где $$$b_i$$$ — коэффициент, зависящий только от $$$i$$$. И тогда, для массива $$$a_1 \geq a_2 \geq \ldots \geq a_n$$$ ответом будет $$$\sum{a_i \cdot b_i}$$$.
Можно исследовать алгоритм, чтобы доказать, что $$$b_i$$$ равно $$$(\frac{n + 1}{2}!)^2 \cdot$$$ $$${n - i - 1} \choose {\frac{n + 1}{2} - 1}$$$.