Max-Min Problem

Max-Min problem is to find a maximum and minimum element from the given array. We can effectively solve it using divide and conquer approach.

In the traditional approach, the maximum and minimum element 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.

• If a₁ is the only element in the array, a₁ is the maximum and minimum.
• If the array contains only two elements a₁ and a₂, then the single comparison between two elements can decide the minimum and maximum of them.
• 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.

Algorithm for Max-Min Problem

Algorithm DC_MAXMIN (A, low, high)
// Description : Find minimum and maximum element from array using divide and conquer approach
// Input : Array A of length n, and indices low = 0 and high = n - 1
// Output : (min, max) variables holding minimum and maximum element of array

if n == 1 then
    return (A[1], A[1])
else if n == 2 then
    if A[1] < A[2] then
        return (A[1], A[2])
    else
        return (A[2], A[1])
    else 
    mid ← (low + high) / 2		
    [LMin, LMax] = DC_MAXMIN (A, low, mid)	
    [RMin, RMax] = DC_MAXMIN (A, mid + 1, high)
    if LMax > RMax  then
        // Combine solution
        max ← LMax
    else 
        max ← RMax
    end
    if LMin < RMin then
        // Combine solution
        min ← LMin
    else
        min ← RMin
    end
    return (min, max)
end

Complexity analysis

The conventional algorithm takes 2(n – 1) comparisons in worst, best and average case.

DC_MAXMIN does two comparisons to determine the minimum and maximum element and creates two problems of size n/2, so the recurrence can be formulated as

T(n) = 0, if n = 1

T(n) = 1, if n = 2

T(n) = 2T(n/2) + 2, if n > 2

Let us solve this equation using interactive approach.

T(n) = 2T(n/2) + 2 … (1)

By substituting n by (n / 2) in Equation (1)

T(n/2) = 2T(n/4) + 2

⇒ T(n) = 2(2T(n/4) + 2) + 2 

=  4T(n/4) + 4 + 2 … (2)

By substituting n by n/4 in Equation (1),

T(n/4) = 2T(n/8) + 2

Substitute it in Equation (1),

T(n) = 4[2T(n/8) + 2] + 4 + 2

= 8T(n/8) + 8 + 4 + 2

=   2³ T(n/2³) + 2³ + 2² + 2¹

.

.

After k – 1 iterations

It can be observed that divide and conquer approach does only [(3n/2) – 2] comparisons compared to 2(n – 1) comparisons of the conventional approach. 

For any random pattern, this algorithm takes the same number of comparisons.

It can be observed that divide and conquer approach does only comparisons compared to 2(n – 1) comparisons of the conventional approach.  For any random pattern, this algorithm takes the same number of comparisons.

Example

Problem: Find max and min from the sequence <33, 11, 44, 55, 66, 22> using divide and conquer approach

Solution:

During the divide step, the algorithm divides the array until it reaches a size of one or two. Once the array size reaches the base case, we may get the maximum and minimum number from each array recursively. This method is continued until all of the subarrays have been processed. The figure below depicts the complete procedure.

The orange cell represents the stage of stepwise division. In the conquer stage, the smallest element from the parent arrays is placed in the green cell, while the largest element is stored in the blue cell.

Some Popular Problems Solved using Divide and Conquer

• Linear Search
• Binary Search
• Convex Hull
• Max-Min Problem
• Larger Integer Multiplication
• Strassen’s Matrix Multiplication
• Finding Exponent Problem
• Merge Sort
• Quick Sort

---

Additional Resource: Read for more detail