# 1-liner Python and 4-liner C++ with rigorous proof (Triangle Inequality!)

• As many has posted here, the answer is simply to sum up the 2nd, 4th, 6th, ...largest values from `nums[]`. But why?

The problem ca be reduced to prove the following statement:
Let

• `P` be an arbitrary n-pair partition for `nums[]`,
• `sum(P)` be such sum of partition `P`,
• `max1`, `max2` be the max and 2nd max values in `nums[]`.

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;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.