Find Maximum and Minimum Element in Array using Divide and Conquer in Java

In this program, you'll learn to Find Maximum and Minimum Element in Array using Divide and Conquer in Java. In this approach, the array is divided into two halves. Then using recursive approach maximum and minimum numbers in each halves are found. Later, return the maximum of two maxima of each half and the minimum of two minima of each half.

As we are dealing with sub problems, we state each sub problem as computing minimum and maximum of a sub array A[p . . q]. Initially, p = 1 and q = A.length, but these values change as we recursive through sub problems.To compute minimum and maximum of A[p . . q]: Divide by splitting into two sub arrays A[p . .r] and A[r+1 . . q], where r is the halfway point of A[p . . q]. Conquer by recursively computing minimum and maximum of the two sub arrays A[p . .r] and A[r+1 . . q]. Combine by computing the overall minimum as the min of the two recursively computed minimum, similar for the overall maximum.

Algorithm :

MaxMinPair dacMaxMin(int i, int j){
// Let a[0:n-1] be a global array.
int max , min ;
if (i == j) max = min = a[i]; // Small problem
   else if (i == j-1) { // Another case of small problem
       if (a[i] < a[j]){ max = a[j] ; min = a[i] ; }
       else { max = a[i] ; min = a[j] ; }
  }
    else{ 
/* If the problem is not small, divide it into subproblems.
Find where to split the set. */
    int mid=(i+j)/2;
    // Solve the subproblems.
    MaxMinPair p = dacMaxMin(i, mid);
    MaxMinPair p1 = dacMaxMin(mid+1, j);
    // Combine the solutions.
    if (p.max < p1.max) max = p1.max;
    else max = p.max;
    if (p.min > p1.min) min = p1.min;
    else min = p.min;
    }
 return new MaxMinPair(max,min);
}

Find Maximum and Minimum Element in Array using Divide and Conquer

When you run the program, the output will be:

Contents of the Array

32 29 34 30 27 28 34 28 37 37 30 35 36 37 37 32 29 26 34 32 

In this array maximum element : 37

In this array minimum element : 26