Divide, solve, and combine under one contract
Divide and conquer splits a problem into smaller pieces, solves them, and combines their results. Correctness requires that the combination actually reconstructs the original answer; merely splitting input is not sufficient.
fun maximum(values: IntArray, from: Int = 0, until: Int = values.size): Int {
require(from >= 0 && until <= values.size && from < until)
if (until - from == 1) return values[from]
val middle = from + (until - from) / 2
return maxOf(maximum(values, from, middle), maximum(values, middle, until))
}
The two intervals are nonempty, disjoint, and cover the original interval. The maximum of their maxima is the global maximum. Time is O(n), with logarithmic recursion depth for balanced splitting. A linear scan is simpler and uses constant workspace, so this example teaches structure rather than a speed improvement.
Exercise
Extend the result to return an index, defining which index wins ties. Compare with a scan over random arrays.
Check: do not assume divide and conquer is inherently faster; account for splitting, combining, allocation, and the baseline algorithm.