我目前正在阅读The Algorithm Design Manual，因此无法进行此练习。
以2n个实数序列作为输入。设计一个O(n log n)算法
将数字划分为n对，并具有分区最小化的属性
一对的最大和。例如，假设我们得到了数字(1,3,5,9)。
可能的分区是((1,3)，(5,9))，((1,5)，(3,9))和((1,9)，(3,5))。这对
这些分区的总和为(4,14)，(6,12)和(10,8)。因此，第三个分区具有
10作为其最大和，这是三个分区中的最小值。
我从一些示例中猜测，该解决方案如下所示:
# in pseudo ruby code
a = [1,3,5,9]
pairs = []
while !a.empty?
pairs << [a.shift, a.pop] # [a.first, a.last]
end
pairs
但是如何证明呢？
最佳答案
该算法之所以有效，是因为当x0，x1，... x2n-1是排序列表时，总是存在包含(x0，x2n-1)的最优解。
证明:
考虑不包含(x0，x2n-1)的任何最佳解决方案。它必须包含对(x0，xa)和(xb，x2n-1)，且x0≤xa≤x2n-1和x0≤xb≤x2n-1。从解决方案中删除这些对，并放在(x0，x2n-1)和(xa，xb)的位置。是否有新的一对“损坏”了解决方案？对(x0，x2n-1)不能具有对，因为它的总和小于或等于(xb，x2n-1)的总和，而xb，x2n-1)是原始的最佳解决方案的成员。由于(xa，xb)的总和小于或等于(xb，x2n-1)的总和，因此两者也不可能造成损害，后者是同一解决方案的成员。我们已经构建了包含(x0，x2n-1)的最优解决方案。
因此，您提供的算法永远不会排除在任何步骤中找到最佳解决方案的可能性，并且当仅剩下两个要配对的值时，必须将它们配对。