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

问题描述

//查找数组中的最大元素.findMax(A)findMaxHelper(A, 0, A.length)findMaxHelper(A，左，右)如果(左 == 右 - 1)返回 A[左]别的max1 = findMaxHelper(A, left, (right + left)/2)max2 = findMaxHelper(A, (right + left)/2, right)如果 (max1 > max2)返回最大值 1别的返回最大值 2

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

有人能帮忙解释一下每一行发生了什么吗?我需要先了解这段代码，然后才能回答问题.

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

解决方案

您正在使用 示例，以更深入地了解该概念.

// 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

I am having a hard time understanding what is happening in this pseudo-code.

Can someone help explain what is happening at each line. I need to understand this code before I can answer the questions.

I know that the function findMax calls the helper function findMaxHelper, then findMaxHelper uses recursion. Other than that, I really don't understand it.

解决方案

You are using Divide and Conquer algorithm for finding the maximum element from the array. First, you are dividing the array into individual elements (divide), then you are comparing the elements (conquer). You are dividing the array using calling findMaxHelper recursively.

The general idea of Divide and conquer is shown in the figure:

Example:

Here max is same as your findMaxHelper function with two arguments i.e. left and right.

Check this example for more in depth understanding of the concept.

这篇关于通过递归查找数组中的最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！