document.write('虽然题目没有时间复杂度与空间复杂度的要求，但是给出的算法的时间复杂度肯定是越低越好。
方法一：蛮力法
查找数组中元素的最大值与最小值并非是一件困难的事情，最容易想到的方法就是蛮力法。具体过程
如下：首先定义两个变量max与min，分别记录数组中最大值与最小值，并将其都初始化为数组的首元
素的值，然后从数组的第二个元素开始遍历数组元素，如果遇到的数组元素的值比max大，则该数组元
素的值为当前的最大值，并将该值赋给max，如果遇到的数组元素的值比min小，则该数组元素的值为
当前的最小值，并将该值赋给min。
算法性能分析：
上述方法的时间复杂度为O(n)，但很显然，以上这种方法称不上是最优算法，因为最差情况下比较的
次数达到了2n-2次(数组第一个元素首先赋值给max与min，接下来的n-1个元素都需要分别跟max与
min比较一次，一次比较次数为2n-2)，最好的情况下比较次数为n-1。是否可以将比较次数降低呢?回
答是肯定的，分治法就是一种更高效的方法。
方法二：分治法
分治法就是将一个规模为n的、难以直接解决的大问题，分割为k个规模较小的子问题，采取各个击
破、分而治之的策略得到各个子问题的解，然后将各个子问题的解进行合并，从而得到原问题的解的一
种方法。
本题中，当采用分治法求解时，就是将数组两两一对分组，如果数组元素个数为奇数个，就把最后一
个元素单独分为一组，然后分别对每一组中相邻的两个元数进行比较，把二者中值小的数放在数组的左
边，值大的数放在数组右边，只需要比较n/2次就可以将数组分组完成。然后可以得出结论：最小值一
定在每一组的左边部分，最大值一定在每一组的右边部分，接着只需要在每一组的左边部分找最小值，
右边部分找最大值，查找分别需要比较n/2-1次和n/2-1次；因此，总共比较的次数大约为
n/2*3=3n/2-2次。
实现代码如下：
class MaxMin:
def __new__(self):
self.max=None
self.min=None
def getMax(self): return self.max
def getMin(self): return self.min
def GetmaxAndmin(self,arr):
if arr==None:
print "参数不合法"
return
i=0
lens=len(arr)
self.max=arr[0]
self.min=arr[0]
#两两分组, 把较小的数放到左半部分, 较大的数放到右半部分
i=0
while i＜(lens-1):
if arr[i]＞arr[i+1]:
tmp=arr[i]
arr[i]=arr[i+1]
arr[i+1]=tmp
i+=2
#在各个分组的左半部分找最小值
self.min=arr[0]
i=2
while i＜lens:
if arr[i]＜self.min:
self.min=arr[i]
i+=2
#在各个分组的右半部分找最大值
self.max=arr[1]
i=3
while i＜lens:
if arr[i]＞self.max:
self.max=arr[i]
i+=2
#如果数组中元素个数是奇数个, 最后一个元素被分为一组, 需要特殊处理
if lens%2=1:
if self.max＜arr[lens-1]:
self.max=arr[lens-1]
if self.min＞arr[lens-1]:
self.min=arr[lens-1]
if __name__=="__main__":
array=[7,3,19,40,4,7,1]
m=MaxMin()
m.GetmaxAndmin(array)
print "max="+str(m.getMax())
print "min="+str(m.getMin))
程序的运行结果为：
max=40
min=1
方法三：变形的分治法
除了以上所示的分治法以外，还有一种分治法的变形，其具体步骤如下：将数组分成左右两部分，先
求出左半部分的最大值和最小值，再求出右半部分的最大值和最小值，然后综合起来，左右两部分的最
大值中的较大值即为合并后的数组的最大值，左右两部分的最小值中的较小值即为合并后的数组的最小
值，通过此种方法即可求合并后的数组的最大值与最小值。
以上过程是个递归过程，对于划分后的左右两部分，同样重复这个过程，直到划分区间内只剩一个元
素或者两个元素为止。
示例代码如下：
class MaxMin:
#返回值列表中有两个元素, 第一个元素为子数组的最小值, 第二个元素为最大值
def getMaxMin(self,array,l,r):
if array==None:
print "参数不合法"
return
list=[]
m=(1+r)/2#求中点
if l==r: #l与r之间只有一个元素
list.append(array[l])
list.append(array[l])
return list
if 1+1=r: #1与r之间只有两个元素
if array[l]＞=array[r]:
max=array[l]
min=array[r]
else:
max=array[r]
min=array[l]
list.append(min)
list.append(max)
return list
#递归计算左半部份
lList=self.get MaxMin(array,l,m)
#递归计算右半部份
rList=self.getMaxMin(array,m+1,r)
#总的最大值
max=lList[1] if (lList[1]＞rList[l]) else rList[1]
#总的最小值
min=lList[0] if (lList[0]＜rList[0]) else rList[0]
list,append(min)
list.append(max)
return list
if __name__=="__main__":
array=[7,3,19, 40,4,7,1]
m=MaxMin()
result=m.getMaxMin(array,0,len(array)-1)
print "max="+str(result[1])
print "min="+str(result[0])
算法性能分析：
这种方法与方法二的思路从本质上讲是相同的，只不过这种方法是使用递归的方式实现的，因此，比
较次数为3n/2-2。
');