Sum of Pair Maximums — Solution & Editorial

Back to the Problem

Sort ascending: position i's element is the maximum of i pairs. (Check: pair-min total + pair-max total = (N−1)·∑a.)

Complexity: O(N log N)