Leetcode每日一题：数组中最大数对和的最小值

Leetcode每日一题 —— 1877. 数组中最大数对和的最小值

思路
第一反应，排序后首尾结合即可。然后第二反应，中等题不会这么简单吧。题目过了，虽然解答简单，但是仔细想想，第一反应只是隐隐约约的直觉，如何证明呢？
我尝试通过推论的方式来证明，如有错漏还请斧正：
排序后，假设2..n-1已满足结论，
0、当只有两个数时，毫无疑问两数结对。
1、n如果与n/2..n-1中的任意一个结对，一定会变成数对和最大值，且超过(1,n)的数对和。
2、n如果与2..n/2-1中的任何一个结对，至少存在一个不影响结果的数对和，导致1..n数组降为2..n-1或更低的已满足结论的数组。
有点抽象，换种方式表达一下，长度8的数组已排好序，分别是a1,a2,a3,a4,a5,a6,a7,a8。
1、(a4,a8)结对，那么剩下的一定是(a1,a7),(a2,a6),(a3,a5)，(a4,a8)一定是最大的，而且超过(a1,a8)。所以这种情况下显然(a1,a8)结对更合适，符合结论。
2、(a2,a8)结对，那么剩下的一定是(a1,a7),(a3,a6),(a4,a5)，其中(a3,a6),(a4,a5)，因为在2..n-1满足，无论有没有都不会将结果变得更小，所以可以忽略，所以剩下a1,a2,a7,a8，这时候显然(a1,a8)(a2,a7)更合适，符合结论。

代码

public int minPairSum(int nums) {
    Arrays.sort(nums);
    int max = 0;
    int len = nums.length;
    for (int i = 0; i < len / 2; i++) {
        max = Math.max(max, nums[i] + nums[len - i - 1]);
    }
    return max;
}

1 post - 1 participant

via - (author: 魔法师)