通过递归在数组中查找最大值

Question

// Find a maximum element in the array.
findMax(A)
   findMaxHelper(A, 0, A.length)

findMaxHelper(A, left, right)
   if (left == right - 1) 
      return A[left]
   else
      max1 = findMaxHelper(A, left, (right + left) / 2)
      max2 = findMaxHelper(A, (right + left) / 2, right)

      if (max1 > max2) 
         return max1 
      else 
         return max2

我很难理解这个伪代码中发生了什么.

有人可以帮助解释每一行发生的事情.在我回答问题之前,我需要先理解这段代码.

我知道函数findMax调用辅助函数findMaxHelper,然后findMaxHelper使用递归.除此之外,我真的不明白.

Answer 1

您正在使用Divide and Conquer算法来查找数组中的最大元素.首先,您将数组划分为单个元素(除法),然后比较元素(征服).您正在使用findMaxHelper递归调用来划分数组.

分而治之的总体思路如下图所示:

例:

这max与你的findMaxHelper函数有两个参数,即left和right.

查看此示例以更深入地了解该概念.