I did a proof which essentially is triangle inequality.

The problem can be reduced to prove the following statement:

Let

Prove if max1 is not paired with max2 in P, and we swap max2 with the value paired with max1 to get partition P', we must have

sum(P') >= sum(P).

Proof: Without losing generality, let pairs (max1, v1) and (max2, v2) in partition P and v1 < max2, then P' has the same pairs as P except (max1, max2) and (v1, v2). We will only need to prove that

min(max1, max2) + min(v1, v2) >= min(max1, v1) + min(max2, v2).

Note that min(x, y) = (x+y-|x-y|)/2 for any number x, y, so we can simplify the inequality above as

max2 - v1 >= min(max2, v2) - min(v1, v2) = (max2+v2-|max2-v2|-(v1+v2-|v1-v2|))/2

= (max2-v1 + |v1-v2| - |max2-v2|)/2.

By triangle inequality, actually, the right hand side

(max2-v1 + |v1-v2| - |max2-v2|)/2 <= (max2-v1 + |max2-v1|)/2 = max2 - v1.

And the proof is complete.

Python:

def arrayPairSum(self, nums): return sum(sorted(nums)[::2])C++:

int arrayPairSum(vector<int>& nums) { sort(nums.begin(), nums.end()); int sum = 0, i = 1; for (int x : nums) sum += x*(i++%2); return sum; }