Максимальное число алгоритма «разделяй и властвуй» в массиве

Question

Я новичок в разделении и завоевании алгоритмов, и мне нужно создать один, чтобы найти наибольшее число в массиве. Ниже мой код, я понимаю, что мне нужно разделить массив на 2 части, а затем рекурсивно найти максимум в каждой части. Затем объедините и найдите самое большое в 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).

После обработки конечных условий, что осталось это рекурсия Вы делите массив на две части и запускаете одну и ту же функцию для каждой части. Это даст вам (в конце концов) ответ.

Имейте в виду, что пространственная сложность такого решения довольно высока. Вы создаете два подмассива каждый раз, когда вызываете рекурсивные функции. Эту проблему можно решить с помощью сигнатуры метода: maxNumber(array, start, end), который сначала будет называться maxNumber(array, 0, array.length), и при каждом рекурсивном запуске вместо копирования массива вы просто вызываете метод с той же ссылкой на массив, но сужаете start и end указатели.