Finding Maximum and Minimum in Design and Analysis of Algorithm (DAA)
The max-min problem is to find a maximum and minimum element from the given array. We can effectively solve it using the divide and conquer approach.
In the traditional approach, the maximum and minimum elements can be found by comparing each element and updating Max and Min values as and when required. This approach is simple but it does (n – 1) comparisons for finding max and the same number of comparisons for finding the min. It results in a total of 2(n – 1) comparisons. Using a divide and conquer approach, we can reduce the number of comparisons.
Divide and conquer approach for Max. Min problem works in three stages.
1. If a1 is the only element in the array, a1 is the maximum and minimum.
2. If the array contains only two elements a1 and a2, then the single comparison between two elements can decide the minimum and maximum of them.
3. If there are more than two elements, the algorithm divides the array from the middle and creates two subproblems. Both subproblems are treated as an independent problem and the same recursive process is applied to them. This division continues until subproblem size becomes one or two.
After solving two subproblems, their minimum and maximum numbers are compared to build the solution of the large problem. This process continues in a bottom-up fashion to build the solution of a parent problem.