minimise-maximum-sum

You are given an array containing 2 \times n elements.You have to partition the numbers in to n pairs with the property that partition minimize the maximum sum of a pair. 

Input
  First line contains T number of test cases. Next line contain N number of pairs.
  Next line contain 2*N positive integers represent elements of an array.
Output
  For each test case print minimum possible maximum sum of a pair.
CONSTRAINTS
1 ≤ T ≤ 100
1 ≤ N ≤ 100000
1 ≤ A[i] ≤ 100000

SAMPLE INPUT
1
3
5 6 2 3 9 8

SAMPLE OUTPUT
11

Explanation

In sample input possible partitions are ((5,6) , (9,2) , (8,3))  and pair sum for these partitons are (11,11,11) so minimum possible maximum sum is 11.
Other possible pairs are ((3,2) , (9,5) , (8,6)) so here minimum possible maximum sum is 14. So 11 is minimum possible maximum sum from all possible pair of partitions.

Source: hackerearth | Difficulty: EASY
Tags: Sorting


Solutions:
p = int(input())
for t in range(p):
	n = int(input())
	maxi=0
	arr = [int(c) for c in input().rstrip().split()]
	arr.sort()
	i=0
	j=2*n-1
	while i<=n:
		if arr[i]+arr[j]>maxi:
			maxi = arr[i]+arr[j]
		i,j=i+1,j-1		
	print(maxi)		


t=eval(input())
for i in range(t):
	n=eval(input())
	arr=[]
	arr=list(map(int,input().split()))
	arr.sort()
	l=len(arr)
	m=l
	arr2=[]
	for k in range(l/2):
		su=arr[k]+arr[m-1]
		arr2.append(su)
		m-=1
	print(max(arr2))
	
		


for _ in range(eval(input())):
	n=eval(input())
	a=list(map(int,input().split()))
	a.sort()
	c=[]
	for x in range(len(a)/2):
		c.append(a[x]+a[len(a)-1-x])
	c.sort()
	print(c[len(c)-1])
		


for _ in range(eval(input())):
	n=eval(input())
	a=list(map(int,input().split()))
	a.sort()
	c=[]
	for x in range(len(a)/2):
		c.append(a[x]+a[len(a)-1-x])
	c.sort()
	print(c[len(c)-1])
		


for _ in range(eval(input())):
	n=eval(input())
	a=list(map(int,input().split()))
	a.sort()
	c=[]
	for x in range(len(a)/2):
		c.append(a[x]+a[len(a)-1-x])
	c.sort()
	print(c[len(c)-1])
		


n=eval(input())
while n:
	p=eval(input())
	i=0
	j=2*p-1
	l=list(map(int, input().split()))
	l.sort()
	A=[]
	while i<j:
		A.append(l[i]+l[j])
		i+=1
		j-=1
	print(max(A))
	n-=1