多路径递归数组中的最大值

Question

我在编写 多路径递归函数 给定一个未排序的整数数组时遇到问题。

std::max(maxArray(a[],first,last))

我知道我需要将数组分成两半并使用比较两个整数的 std::max 函数，例如：

return std::max(maxArray(a[],Not sure, Not Sure),maxArray(a[], Not sure, Not sure))

我熟悉二进制搜索算法。但是，我很难看到如何解决这个问题，而不仅仅是比较数组左侧和右侧的两个数字。这两个数字不会 return 比较 2 中的较大者然后被丢弃吗？

我看过其他关于同样问题的帖子，但它不符合给出的伪代码。任何帮助将不胜感激。

Answer 1

我很难理解你对你不理解的内容的解释。但是你得到的代码背后的原理是，如果你将一个数组分成两半并（递归地）找到每一半的最大值，那么整个数组的最大值就是这两个值中的较大者。

像这样

int maxArray(const int* a, int left, int right)
{
    if (left == right)
    {
        return a[left];
    }
    else
    {
        int mid = (left + right)/2;
        return std::max(
            maxArray(a, left, mid),
            maxArray(a, mid + 1, right));
    }
}

多路径递归数组中的最大值

Multipath recursion Maximum Value in Array

c++

arrays

recursion

binary-search