2.4.3 查找数组中的最大值

2.4.3  查找数组中的最大值

假设有一个整型数组anArray，要在这个数组中找出最大值。创建一个迭代解决方案并不困难，但此处考虑使用递归方案:
 

if (anArray has only one entry)  
maxArray(anArray) is the entry in anArray  
else if (anArray has more than one entry)  
maxArray(anArray) is the maximum of  
maxArray(left half of anArray) and maxArray(right half of anArray) 

注意，该策略符合本章开头曾出现的折半查找算法的分而治之模型。所谓分而治之，就是通过分解问题并控制子问题逐步推进，如图2-12所示。但这个算法与折半查找算法有所不同。折半查找算法每步只控制一个子问题，而maxArray控制两个子问题。由于两个子问题都涉及递归，因此这种方法被称为多路径递归(multipath recursion)。当maxArray解决子问题后必须协调两个解决方案，也就是说必须查找两个最大值之中的最大值。图2-13显示了在包含1、6、8和3的数组(用<1,6,8,3>表示)中查找最大整数的计算过程。

注释：maxArray每步都要解决两个子问题

问题8 根据前面给出的伪代码，定义返回数组中最大值的C++递归函数maxArray。