Java recursive difference in array

Question

I'm currently learning Java and I stumbled on an exercise I can't finish.

The task is to write a recursive method that takes an array and returns the difference of the greatest and smallest value.

For example {12, 5, 3, 8} should return 5 (8 - 3). It is important to note that it is only allowed to compare values in their right order (result = rightValue - leftValue). For example 12-3 = 9 would not be allowed. Think of it like stock values. You want to find out which time to buy and sell the stocks to make the largest profit.

It was quiet easy to implement this iterative but I have no idea how to do it recursive. Also it is part of the task to solve it by using divide and conquer.

Answer 1

I've used divide and conquer approach here. I believe the trick here is to include middle in both the arrays that we're splitting the main array into.

/* edge cases ignored here */

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);

}