Difficulty: Medium

这道题说到底不难，就是首尾相加就可以了。凭知觉做就可以。
题目要求是最大数对和最小，也就是要求每一个数对的和分布均匀，很容易想到首尾相加。那么如何证明呢？

假如有四个数，a>b>c>d。如果我们不收尾相加，即a+c和b+d。如果收尾相加，就是a+d和b+c。

直观上看，因为四个数的和是定值，我们实际上是要减少它们的差，也就是希望有|(a+c)-(b+d)|>|(a+d)-(b+c)|....(1)。

数学上看，max(m,n)=(m+n+|m-n|)/2。
max(a+c,b+d)=(a+b+c+d)/2+|(a+c)-(b+d)|/2。即上式。

对 (1) 式，LHS=|(a-b)+(c-d)|>|(a-b)-(c-d)|=RHS, 其中用到了a-b>0, c-d>0。这样就证明了，四个数的时候必须要收尾相加。

进一步推广，如果有序列a1>a2>a3...>an，和b1<b2<b3...<bn，则也必须要a1+b1, a2+b2...an+bn。否则a和b中的连线必然有交叉，而此时总可以通过对调同一序列中的元素来解开交叉。

我们注意到交换连线两端的两个数字，即一个在序列a中一个在序列b中，不会影响最终结果(即使此时会破坏a,b各自的有序性)。

如果a和b都是各自有序的，但a>b并不保证，那么对于结果a1+b1, a2+b2...an+bn来说，我们总可以通过对调同一序列中的元素或连线两端的元素来解除交叉，使结果降低。

于是就有了这题的首尾配对相加的答案。我上面给的证明不好，可以见Leetcode官方的答案。

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        int n=nums.size()/2;
        sort(nums.begin(), nums.end());
        for(int i=0;i<n;i++){
            nums[i]+=nums[nums.size()-1-i];
        }
        return *max_element(nums.begin(), nums.begin()+n);
    }
};