阵列中的分治算法最大数目

Question

我是分割和征服算法的新手，需要构造一个算法才能找到数组中的最大数目。下面是我的代码，我了解我需要将数组分为2部分，然后递归地找到每个部分中的最大值。然后，合并并找到两个部分中最大的一个。下面是我的代码，我正在努力找出如何递归调用函数以在每个部分中找到最大值的方法。

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以及1）。

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