Finding Max value in an array using recursion

问题:

For one of the questions i was asked to solve, I found the max value of an array using a for loop, so i tried to find it using recursion and this is what I came up with:

public static int findMax(int[] a, int head, int last) {

    int max = 0;
    if (head == last) {
        return a[head];
    } else if (a[head] < a[last]) {
        return findMax(a, head + 1, last);
    } else {
        return a[head];
    }
}

So it works fine and gets the max value, but my question is : is it ok to have for the base case return a[head] and for the case when the value at the head is > the value at last?

回答1:

You could just as easily do it with only one counter, just the index of the value you want to compare this time:

public static int findMax(int[] a, int index) {
    if (index > 0) {
        return Math.max(a[index], findMax(a, index-1))
    } else {
        return a[0];
    }
}

This much better shows what is going on, and uses the default "recursion" layout, e.g. with a common base step. Initial call is by doing findMax(a, a.length-1).

回答2:

It's actually much simpler than that. The base case is if you've reached the end of the array (the 'else' part of the ternary control block below). Otherwise you return the max of the current and the recursive call.

public static int findMax(int[] a) {
    return findMax(a, 0);
}
private static int findMax(int[] a, int i) {
    return i < a.length
           ? Math.max(a[i], findMax(a, i + 1))
           : Integer.MIN_VALUE;
}

At each element, you return the larger of the current element, and all of the elements with a greater index. Integer.MIN_VALUE will be returned only on empty arrays. This runs in linear time.

回答3:

I would solve this by dividing the array in to the half on each recursive call.

 findMax(int[] data, int a, int b)

where a and b are array indices.

The stop condition is when b - a <= 1, then they are neighbours and the max is max(a,b);

The initial call:

 findMax(int[] data, int 0, data.length -1);

This reduces the maximum recursion depth from N to log2(N).
But the search effort still stays O(N).

This would result in

int findMax(int[] data, int a, int b) {
   if (b - a <= 1) {
     return Math.max(data[a], data[b]);
   } else {
     int mid = (a+b) /2; // this can overflow for values near Integer.Max: can be solved by a + (b-a) / 2; 
     int leftMax =  findMax(a, mid);
     int rightMax = findMax(mid +1, b);
     return Math.max(leftMax, rightMax);
   }
}

回答4:

What about this one ?

public static int maxElement(int[] a, int index, int max) {
    int largest = max;
    while (index < a.length-1) {
        //If current is the first element then override largest
        if (index == 0) {
            largest = a[0];
        }
        if (largest < a[index+1]) {
            largest = a[index+1];
            System.out.println("New Largest : " + largest); //Just to track the change in largest value
        }
        maxElement(a,index+1,largest);
    }
    return largest;
}

回答5:

I know its an old Thread, but maybe this helps!

public static int max(int[] a, int n) {
        if(n < 0) {
            return Integer.MIN_VALUE;
        }
        return Math.max(a[n-1], max(a, n - 2));

    }

回答6:

I came across this thread and it helped me a lot. Attached is my complete code in both recursion and divide&conquer cases. The run time for divide&conquer is slightly better than recursion.

//use divide and conquer.
public int findMaxDivideConquer(int[] arr){
    return findMaxDivideConquerHelper(arr, 0, arr.length-1);
}
private int findMaxDivideConquerHelper(int[] arr, int start, int end){
    //base case
    if(end - start  <=  1) return Math.max(arr[start], arr[end]);
    //divide
    int mid = start + ( end - start )/2;
    int leftMax =findMaxDivideConquerHelper(arr, start, mid);
    int rightMax =findMaxDivideConquerHelper(arr, mid+1, end);
    //conquer
    return Math.max( leftMax, rightMax );
}

// use recursion. return the max of the current and recursive call
public int findMaxRec(int[] arr){
    return findMaxRec(arr, 0);
}
private int findMaxRec(int[] arr, int i){
    if (i == arr.length) {
        return Integer.MIN_VALUE;
    }
    return Math.max(arr[i], findMaxRec(arr, i+1));
}

回答7:

class Test
{
    int high;
    int arr[];
    int n;
    Test()
    {
        n=5;
        arr = new int[n];
        arr[0] = 10;
        arr[1] = 20;
        arr[2] = 30;
        arr[3] = 40;
        arr[4] = 50;
        high = arr[0];
    }
    public static void main(String[] args)
    {
       Test t = new Test();
       t.findHigh(0);
       t.printHigh();
    }
    public void printHigh()
    {
        System.out.println("highest = "+high);
    }
    public void findHigh(int i)
    {
        if(i > n-1)
        {
            return;
        }
        if(arr[i] > high)
        {
            high = arr[i];
        }
        findHigh(i+1);
        return;
    }
}

回答8:

You can do it recursively as follows.

Recurrent relation it something like this.

   f(a,n)   = a[n]   if n == size
            = f(a,n+1) if n != size

Implementation is as follows.

   private static int getMaxRecursive(int[] arr,int pos) {
         if(pos == (arr.length-1)) {
                return arr[pos];
         } else {           
                return Math.max(arr[pos], getMaxRecursive(arr, pos+1));
         }
   }

and call will look like this

      int maxElement = getMaxRecursive(arr,0);

回答9:

its not okay! your code will not find the maximum element in the array, it will only return the element that has a higher value than the elements next to it, to solve this problem,the maximum value element in the range can be passed as argument for the recursive method.

    private static int findMax(int[] a, int head, int last,int max) {
    if(last == head) {
        return max;
    }
    else if (a[head] > a[last]) {
            max = a[head];
            return findMax(a, head, last - 1, max);
        } else {
            max = a[last];
            return findMax(a, head + 1, last, max);
        }
}

回答10:

  public int GetMax(int [] A, int index)  {

         index += 1;
         if (index >= A.Length) return 0;
         return Math.Max(A[index], GetMax(A, index + 1));

     }

回答11:

int maximum = getMaxValue ( arr[arr.length - 1 ], arr, arr.length - 1 );

public static int getMaxValue ( int max, int arr[], int index )
{
    if ( index < 0 )
        return max;
    if ( max < arr[index] )
        max = arr[index];
    return getMaxValue ( max, arr, index - 1 ); 
}

I felt that using a tracker for current maximum value would be good.

回答12:

If you are wondering how to get the max int of a list using recursion:

public int maxInt(MyList<Integer> m) {

    // -----------------------------
    // VARIABLES
    // -----------------------------
    int maxValue = 0;
    int scenario = 0;

    // -----------------------------
    // SET OF OPS
    // -----------------------------

    // -----------------------------
    // I. SCENARIO IDENTIFICATION
    // -----------------------------

    // Rule 1. MyList is empty
    if (m.length() == 0)
        scenario = 1;

    // Rule 2. MyList is non-empty
    else
        scenario = 2;

    // -----------------------------
    // II. SCENARIO IMPLEMENTATION
    // -----------------------------
    switch (scenario) {

    case 1:
        maxValue = -1;

        break;

    case 2:

        // 1. We get the first element of MyList
        int first = m.getElement(0);

        // 2. We remove the first element from MyList we just checked
        m.removeElement(0);

        // 3. We recursively solve the smaller problem
        maxValue = maxInt(m);

        // 4. We compute the final result, based on the value that we were
        // hosting.
        if (first > maxValue) {
            maxValue = first;
        }
        // 5. We also add the element back to m, so as to not to modify its
        // original state
        m.addElement(0, first);

        break;
    }
    return maxValue;

}