In the Divide and Conquer algorithm for finding the maximum and minimum…

Concept

Divide and Conquer solves a problem by splitting it into smaller independent subproblems, solving each subproblem recursively, and then merging the sub-results in a combine step. For the max–min problem, once the left half's maximum and minimum and the right half's maximum and minimum are known, the array's overall maximum can only be one of these two half-maxima (every element belongs to one half or the other), and the overall minimum can only be one of these two half-minima.

Applying it to this problem

1. Split the array A[low..high] at the midpoint into A[low..mid] and A[mid+1..high].

2. Recursively find (max1, min1) for the left half and (max2, min2) for the right half.

3. In the combine step, compare max1 and max2 and keep the larger value as the overall maximum.

4. Compare min1 and min2 and keep the smaller value as the overall minimum.

5. Return this (max, min) pair as the result of the current recursive call — this comparison-based merge is exactly how the two halves' results are combined.

Cross-check

Take A = [3, 7, 2, 9, 4, 1]. The left half [3, 7, 2] gives max1 = 7, min1 = 2; the right half [9, 4, 1] gives max2 = 9, min2 = 1. Combining: max(7, 9) = 9 and min(2, 1) = 1 — exactly the true maximum and minimum of the full array, confirming the compare-based combine step. This combine step runs in constant time per merge, so the overall algorithm stays O(n), matching (and, with the paired-comparison refinement, slightly beating) a direct single-pass scan.

So the left and right sub-results are combined by comparing the two maxima and comparing the two minima — not by averaging, adding, or multiplying them.