java - 分而治之算法数组中的最大数量

Question

我是分治算法的新手，需要构造一个算法来查找数组中的最大数字。下面是我的代码，我知道我需要将数组分为两部分，然后递归地找到每个部分中的最大值。然后，合并并找到两部分中最大的部分。下面是我的代码，我正在努力弄清楚如何递归调用函数来找到每个部分的最大值。

private static int problem(int[] histogram) {
        int left = 0;
        int right = histogram.length -1;
        if (left == right){
            return left;
        }
        int middle = (left + right)/2;

        return -1;
    }    

另外，这会是 O(n log n) 时间复杂度吗？

Answer 1

static int maxNumber(int[] array) {
        switch (array.length) {
            case 1:
              return array[0];
            case 2:
              return array[0] > array[1]
                ? array[0]
                : array[1];
            default:
              int left = maxNumber(Arrays.copyOfRange(array, 0, (int) (array.length / 2)));
              int right = maxNumber(Arrays.copyOfRange(array, (int) (array.length / 2), array.length));
              return left > right
                ? left
                : right;
        }
    }

如您所见，在递归中最重要的部分是处理结束条件。告诉递归何时停止。在我们的例子中，当数组中有一个或两个数字时我们就停止(如果我们将数组除以 3 个元素，我们会得到一个包含 2 的元素，一个包含 1 的元素)。

处理完结束条件后，剩下的就是递归了。您将数组分为两部分，并在每个部分上运行相同的函数。这将(最终)给你答案。

请记住，这种解决方案的空间复杂度相当高。每次调用递归函数时都会创建两个子数组。这可以通过以下方法签名来解决:maxNumber(array, start, end)，它首先被称为 maxNumber(array, 0, array.length) 和每次递归运行时，您只需使用相同的数组引用调用该方法，而不是复制数组，但会缩小 start 和 end 指针。