分治法求序列中的最大和次大元素

分治法是指将一个复杂的，规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题相互独立且与原问题形式相同，递归的解这些子问题，然后将各子问题的解合并得到原问题的解的算法设计策略。

对于无序序列 a[low...high]，采用分治法求最大元素 max1 和次大元素 max2 的过程如下：

[if !supportLists]（1）  [endif]若 a[low...high]中只有一个元素，则 max1 = a[low],max2 = -INF-(-oo)。

[if !supportLists]（2）  [endif]若 a[low...high]中只有两个元素，则 max1 = max{a[low],a[high]},max2=min{a[low],a[high]}。

[if !supportLists]（3）  [endif]若 a[low...high]中有两个以上元素，按中间位置 mid = (low + high)/2 划分为 a[low...mid]和 a[mid + 1...high]两个区间（注意左区间包含 a[mid]元素）。求出左区间的最大元素 lmax1 和次大元素 lmax2，求出https://www.523it.com/右区间的最大元素 rmax1 和次大元素 rmax2。

若 lmax1 > rmax1，则 max1 = lmax1，max2 = max{lmax2，rmax1}；否则 max1 = rmax1,max2 = max{lmax1,rmax2}。

例如：

    对于 a[0...4] = {5,2,1,4,3},mid = (0 + 4)/2 = 2，划分为左区间 a[0...2] = {5,2,1}，右区间 a[3...4] = {4,3}。在左区间中求出 lmax1 = 5,lmax2 = 2，在右区间中求出 rmax = 4，rmax2 = 3。所以 max1 = max{lmax1,rmax1} = 5,max2

= max{lmax2,rmax1} = 4。

对于 solve(a,0,n-1,max1,max2)调用，假设其执行时间为 T(n)，当 n=1 或 2 时，起执行此数为 1，当 n>2 时，不断分解 n 并递归调用其 solve 方法，直至 n=1 或 2，其比较次数的递推式如下：

T(1) = T(2) = 1

T(n) = 2T(n/2) + 1             //n>2，合并的时间为 O(1)

可以推导出 T(n) = O(n)。