Find Max Recursion Algorithm
The Find Max Recursion Algorithm is a powerful and efficient technique used to determine the maximum value within a given list or array of numbers. This algorithm works by employing the divide-and-conquer approach, which involves breaking down the problem into smaller subproblems, solving these subproblems recursively, and then combining the solutions to form the overall solution. In the context of finding the maximum value, the algorithm recursively divides the list into smaller parts until it reaches a point where it can easily compare and find the maximum value. This is typically done by dividing the list into two halves and finding the maximum value in each half, and then comparing the maximum values obtained from both halves to determine the overall maximum value.
The Find Max Recursion Algorithm begins by checking the base case, which is when the length of the list is either one or two elements. In this scenario, the maximum value can be easily determined by comparing the elements directly. If the list has more than two elements, the algorithm proceeds to divide the list into two halves and recursively calls itself on each half. Once the maximum values from each half are determined, the algorithm compares these values to find the overall maximum value. This process continues until all the subproblems have been solved, and the final maximum value is returned. The efficiency and elegance of this algorithm come from its ability to reduce the problem size at each recursive step, eventually leading to a simple comparison of two values for the base case.
package Maths;
public class FindMaxRecursion {
public static void main(String[] args) {
int[] array = {2, 4, 9, 7, 19, 94, 5};
int low = 0;
int high = array.length - 1;
System.out.println("max value is " + max(array, low, high));
}
/**
* Get max of array using divide and conquer algorithm
*
* @param array contains elements
* @param low the index of the first element
* @param high the index of the last element
* @return max of {@code array}
*/
public static int max(int[] array, int low, int high) {
if (low == high) {
return array[low]; //or array[high]
}
int mid = (low + high) >>> 1;
int leftMax = max(array, low, mid); //get max in [low, mid]
int rightMax = max(array, mid + 1, high); //get max in [mid+1, high]
return leftMax >= rightMax ? leftMax : rightMax;
}
}
