'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?

javarecursion


Solution 1:[1]

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.

Solution 2:[2]

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

Solution 3:[3]

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

Solution 4:[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;
}

Solution 5:[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));

    }

Solution 6:[6]

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

Solution 7:[7]

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

Solution 8:[8]

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

Solution 9:[9]

Optimized solution

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

        int max = 0, max1 = 0;

        if (head == last) {
            return a[head];

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

        if (max >= max1) {
            max1 = max;
        }
        return max1;


    }

    public static void main(String[] args) {
        int arr[] = {1001, 0, 2, 1002, 2500, 3, 1000, 7, 5, 100};
        int i = findMax(arr, 0, 9);
        System.out.println(i);
    }
}

Solution 10:[10]

Thanks @Robert Columbia for the suggestion!

Update: This following function is going to recursively start from index 0 and it will keep adding to this index value till it's equal to the Length of the array, if it's more we should stop and return 0. Once we're doing that, we need to get the max of every two items in the array so, for example:

A = [1 , 2 , 3 ];

A[0] ( 1 ) vs A[1] ( 2 ) = 2 
A[1] ( 2 ) vs A[2] ( 3 ) = 3
Max(2,3) = 3 ( The answer )  





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

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

 }

Solution 11:[11]

static int maximumOFArray(int[] array,int n) {
    
    
    int max=Integer.MIN_VALUE;
    
    if(n==1) return array[0];
    else
        max=maximumOFArray(array, --n);

    max= max>array[n] ? max : array[n];
    return max;
        
}

Solution 12:[12]

private static int getMax(int [] arr, int idx) {

    if (idx==arr.length-1 ) return arr[idx];

    
    return Math.max(arr[idx], getMax (arr,idx+1 ));
}

Solution 13:[13]

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.

Related Questions