Recursive function to difference between two values in array

Question

I'm using Java.

I need to implement a recursive function that calculates the difference between each two values and returns for me array in size 2 [MAXIMUM_DIFF, STARTINDEX].

For the following array:

arr = {1, 4, 60, -10, 2, 7, 56, -10}

The recursive method returns array in size 2: [70,2] because the maximum difference is 70 (60-(-10)=70) and the index of 60 is 2.

I have 90% from the solution:

public static int[] getMax(int[] arr) {

    int [] retArr = new int[2];

    if(arr.length == 1)
        return retArr;
    else {
        return getMax(arr, retArr);
    }

}

public static int[] getMax(int[] arr, int[] retArr) {
    if(retArr[1] == arr.length - 1)
        return retArr;

    int currentMaxVal = arr[retArr[1]] - arr[retArr[1] + 1];

    if(currentMaxVal > retArr[0]) {
        retArr[0] = currentMaxVal;
    }

    retArr[1] = retArr[1] + 1;

    return getMax(arr, retArr);

}

But the result is[70,7] instead of [70,2] because this line retArr[1] = retArr[1] + 1;

This is because I don't know where to save the index, So how can I save the index?

*I'm not sure about the second param of getMax(int [] arr, int []retArr) Its can be different maybe

I cant add another parameters, Maybe to change the second param of getMax(int [] arr, int []retArr), And I can't use static variables

why don't you pass another parameter called index and update it only when it goes inside the compare if statement — zenwraight
– zenwraight, Commented May 24, 2017 at 19:54

Tezra · Accepted Answer · 2017-05-24 20:53:33Z

if(currentMaxVal > retArr[0])
{
  retArr[0] = currentMaxVal;
}

retArr[1] = retArr[1] + 1;

Should be

if(currentMaxVal > retArr[0])
{
  retArr[0] = currentMaxVal;
  retArr[1] = currentIndex;
}

And currentIndex should be an additional parameter passed to the function. (and other references to current index updated accordingly)

UPDATE:

I think the point here is to understand "divide and conquer", where you break up the problem into a smaller problem, and then sort through for the best one. Something like this (if a bit more awkward then a normal case)

public static int[] getMax(int[] arr, int[] retArr) {
    // Return case
    if (retArr[1] >= arr.length - 1)
        return new int[] { Integer.MIN_VALUE, retArr[1] };

    // Save context
    int index = retArr[1];
    int value = arr[index] - arr[index + 1];

    // Call recursion
    retArr[1]++;
    int[] temp = getMax(arr, retArr);

    // Return best between current case and recursive case
    if (temp[0] > value)
        return temp;
    else
        return new int[] { value, index };
}

Each call (or stack) of the recursive function is its own context. That means variables declared in it won't be overwritten in the recursive calls. The idea is that you break a hard problem down recursively until you can't break it down any further. Then you solve it by putting together the results of each call one at a time until you have your final answer. (This works better with less trivial cases like the fibonacci sequence) Also note that anything that can be done in a loop will always be more efficient then recursion.

Hi, Thank you, see my edit right now, I cant add another parameters to the function, I can add only one parameter
@Evyatar I can try. Updated answer. To help more, I need to know which part you don't fully understand.

Collectives™ on Stack Overflow

Recursive function to difference between two values in array

1 Answer 1

4 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Related