Рекурсивная разность Java в массиве

Question

В настоящее время я изучаю Java, и я наткнулся на упражнение, которое я не могу закончить.

Задача состоит в том, чтобы написать рекурсивный метод, который принимает массив и возвращает разницу наибольшего и наименьшего значения.

Например, {12, 5, 3, 8} должен вернуть 5 (8 - 3). Важно отметить, что разрешено сравнивать значения в правильном порядке (result = rightValue - leftValue). Например, 12-3 = 9 не будет разрешено. Подумайте об этом, как о стоимости акций. Вы хотите узнать, какое время покупать и продавать акции, чтобы получить наибольшую прибыль.

Было очень легко реализовать этот итеративный вариант, но я понятия не имею, как это сделать рекурсивно. Также это часть задачи по ее решению, используя разделение и завоевание.

Answer 1

Я использовал разделяй и властвуй подход здесь. Я считаю, что трюк здесь состоит в том, чтобы включить средний размер в оба массива, в которые мы разбиваем основной массив.

/* крайние случаи игнорируются здесь */

int findMax(int[] arr, int left, int right){ 

if(right-left == 1) return (arr[right]-arr[left]); 

int middle = left + (right-left)/2; 

int max1 = findMax(arr, left, middle); 
int max2 = findMax(arr, middle, right); 

if(max1 >= 0 && max2 >= 0) return max1+max2; 

else return Math.max(max1,max2); 

} 

Answer 2

Алгоритм (это в значительной степени задача сортировки, то шаг вычитания тривиально)

1) Сначала сортировать массивы (использовать рекурсивную сортировку слияния для больших массивов и рекурсивных вставок для небольших массивов).

сортировка слиянием (https://en.wikipedia.org/wiki/Merge_sort)

Вставка рода (https://en.wikipedia.org/wiki/Insertion_sort)

2) Используйте массивы наименьший индекс [0], чтобы получить наименьшее значение & индекс [array.length-1], чтобы получить наибольший

3) вычислить разницу (не знаю, что вы имеете в виду правильном порядке?)

Answer 3

Ну я не думаю, что рекурсия является очень эффективным в этом. Вы, вероятно, никогда не сделаете этого (кроме домашней работы). Что-то, как это будет делать:

int findGreatestDifference(Vector<Integer> numbers, int greaterDifference){ 
    if(numbers.size() == 1) //return at last element 
     return greaterDifference; 
    int newDifference = (numbers.get(0) - numbers.get(1)); 
    if (newDifference > greaterDifference) 
     greaterDifference = newDifference; 

    numbers.remove(numbers.size() - 1); 
    findGreatestDifference(numbers, greaterDifference); 
    return greaterDifference; 
} 

первый раз, когда вы называете, передайте 0 как большая разность, и снова я не нахожу это как эффективный способ сделать это. Итерация была бы лучше для этого.

Надеюсь, это поможет.