The pair sum of a pair (a,b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs.


	For example, if we have pairs (1,5), (2,3), and (4,4), the maximum pair sum would be max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8.


Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that:


	Each element of nums is in exactly one pair, and
	The maximum pair sum is minimized.


Return the minimized maximum pair sum after optimally pairing up the elements.

&nbsp;
Example 1:

Input: nums = [3,5,2,3]
Output: 7
Explanation: The elements can be paired up into pairs (3,3) and (5,2).
The maximum pair sum is max(3+3, 5+2) = max(6, 7) = 7.


Example 2:

Input: nums = [3,5,4,2,4,6]
Output: 8
Explanation: The elements can be paired up into pairs (3,5), (4,4), and (6,2).
The maximum pair sum is max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8.


&nbsp;
Constraints:


	n == nums.length
	2 &lt;= n &lt;= 105
	n is even.
	1 &lt;= nums[i] &lt;= 105

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        pair_sum = []
        nums.sort()
        for i in range(len(nums)//2):
            pair_sum.append(nums[i]+nums[len(nums)-i-1])
        return max(pair_sum)
class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);

        int output = Integer.MIN_VALUE;

        //This is greedy, so n/2 pairs must be from start and end and move inwards
        for(int i=0, j=nums.length - 1; i<nums.length/2; i++, j--)
        {
            output = Math.max(output, nums[i] + nums[j]);
        }

        return output;
    }
}
class Solution {
public:
    int minPairSum(vector<int>& nums){
	    //sort the array
        sort(nums.begin(),nums.end());
        int start=0,end=nums.size()-1,min_max_pair_sum=0;
		//Observe the pattern of taking the first and last element, second and second last element... and soo onn.. 
		//would help you to minimize the maximum sum.
        while(start<end){
            min_max_pair_sum=max(min_max_pair_sum,nums[start++]+nums[end--]);
        }
        return min_max_pair_sum;
    }
};
/**
 * @param {number[]} nums
 * @return {number}
 */
var minPairSum = function(nums) {
    nums.sort((a,b) => a-b);
    let max = 0;
    for(let i=0; i<nums.length/2; i++){
        max = Math.max(max , nums[i] + nums[nums.length-1-i]);
    }
    return max;
};
Minimize Maximum Pair Sum in Array