Finding the maximum value in an array using recursion

Question

For one of the questions that I was asked to solve, I found the maximum value of the 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]; } } 

Thus, it works fine and gets the maximum value, but my question is: is it normal for the base case to return [head] and for the case when the value at the beginning is> the value finally?

Answer 1

You can just as easily do this with just one counter, just a pointer to 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 happening, and uses the default recursion layout, for example. with a common milestone. The initial call is made by findMax(a, a.length-1) .

Answer 2

This is actually a lot easier. The main case is if you have reached the end of the array (the "else" part of the tronar control unit below). Otherwise, you will return the maximum current and 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; } 

In each element, you return most of the current element and all elements with a large index. Integer.MIN_VALUE will only return on empty arrays. This runs in linear time.

Answer 3

I would solve this by dividing the array by half for each recursive call.

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

where a and b are the indices of the array.

The stopping condition is when b - a <= 1 , then they are neighbors, and max max (a, b);

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 is still O (N).

This will lead to

 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 + (ba) / 2; int leftMax = findMax(a, mid); int rightMax = findMax(mid +1, b); return Math.max(leftMax, rightMax); } } 

Answer 4

How about this?

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

Answer 5

I know his old topic, but maybe it 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)); } 

Answer 6

I stumbled upon this topic and it helped me a lot. Attached is my complete code, both in cases of recursion, and in the matter of division and amp; The runtime 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)); } 

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

Answer 8

You can do this recursively as follows.

A recurring attitude is something like this.

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

The 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 the call will look like this

  int maxElement = getMaxRecursive(arr,0); 

Answer 9

it is not normal! your code will not find the maximum element in the array, it will only return an element with a higher value than the elements next to it. To solve this problem, the maximum value element in the range can be passed as an argument to 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); } } 

Answer 10

Thanks @ Robert Columbia for the offer!

Update: this next function will recursively start at index 0, and it will continue to add to this index value until it becomes equal to the length of the array, if it is larger, we must stop and return 0. Once we do this, we need to get maximum of every two elements in the array, 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)); } 

Answer 11

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

Answer 12

 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 the current maximum value would be good.

Answer 13

If you are wondering how to get max int from 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; }