Unconventional Pairs

Sort the array. That is the whole trick.

Once the numbers are sorted as

$b_1 \le b_2 \le \dots \le b_n,$

we claim the best pairing is:

$$(b_1,b_2), (b_3,b_4), \dots, (b_{n-1},b_n).$$

Then the answer is simply:

$$\max_{i=1}^{n/2} (b_{2i} - b_{2i-1}).$$

Why adjacent pairing is optimal

Look at the smallest remaining number, say $b_1$.

Suppose some optimal solution pairs it with $b_j$ where $j>2$. Then $b_2$ must be paired with some other number $b_k$.

So the solution contains these two pairs:

$$(b_1,b_j), \quad (b_2,b_k).$$

Now replace them with:

$$(b_1,b_2), \quad (b_j,b_k).$$

This does not make the maximum pair difference worse:

• $b_2-b_1 \le b_j-b_1$, so the new pair $(b_1,b_2)$ is no worse than the old pair containing $b_1$.
• For $(b_j,b_k)$, its difference is also bounded by one of the old two gaps, depending on whether $k<j$ or $k>j$.

So if there is an optimal solution where $b_1$ is not paired with $b_2$, we can modify it into another optimal solution where they are paired. Nice little exchange argument, no drama.

After pairing $b_1$ with $b_2$, the same logic applies to the remaining sorted numbers. Therefore, there is always an optimal solution that pairs adjacent sorted elements.

Algorithm

For each test case:

1. Read $n$ and the array.
2. Sort the array.
3. For every even-positioned pair in sorted order, compute the difference:

$$b_2-b_1,\ b_4-b_3,\ \dots,\ b_n-b_{n-1}.$$

4. Output the maximum of those values.

Complexity

Sorting dominates:

$$O(n \log n)$$

per test case, with total $n \le 2\cdot 10^5$, so this is easily fine.