同时求最大值与最小值（看似简单却值得思考~）

1. 问题描述：

给定一个数组，分别输出数组中的最大值与最小值。

2. 题解：

（1）蛮力法：

这个问题未免显得过于简单，从n个数中找到最大值或者最小值，只需要比较n-1次即可，因此要想找出最大值和最小值，只需要比较2*(n-1)即2n-2次。但是，是否可以做出优化呢？接下来我们给出只需要比较2n/3 左右即可完成的方法

（2）分治算法

分治算法的核心的将一个规模比较大的问题拆分成一个个小的子问题，如下图所示：

当我们将问题拆分成只含有两个元素时，只需要一次比较即可同时得到最大值和最小值，我们来计算一下复杂度：

算法: MaxMin(A)
// 输入：数组A[i...j]
// 输出：数组A[i...j]中的max和min
if j - i + 1 = 1    Then 输出A[i], A[i],算法结束
if j - i + 1 = 2    Then
    if A[i] < A[j]    Then 输出A[i], A[j], 算法结束
        else    输出 A[j], A[i], 算法结束
k  (j - i + 1) / 2
m1, M1  MaxMin(A[i : k]);
m2, M2  MaxMin(A[k + 1 : j]);
m  min(m1, m2);
M  min(M1, M2);
输出m, M

（3）伪分治算法

我们先两两分组，然后一组两个数之间只需要进行一次比较即可得到最大值和最小值。现在我们有
⌊n/2⌋ 个最小值和 ⌊n/2⌋ 个最大值，如果最初为奇数个元素，那么最大值肯定在⌊n/2⌋个最大值和轮空元素之间产生，同理，最小值肯定在⌊n/2⌋个最小值和轮空元素之间产生。之后再使用冒泡的思想从这些元素中找到最大值和最小值即可得到最终解。

时间复杂度（比较次数）计算如下：