Divide and Conquer
Divide and Conquer is a popular technique to solve algorithmic problems. We’ve already seen some techniques to solve algorithmic problems. The greedy approach takes the most optimal result at each step. Dynamic programming constructs the current state based on the previous ones. In the case of the divide and conquer approach, we split the problem into smaller sub-problems and solve those one-by-one while combining the result at the end. So, we divide the problem into sub-problems and conquer the initial problem by combining the solutions of the sub-problems.
Challenge
Imagine that you are given 512 numbers and there are 512 specialized computers (very small and specialized computers) that can only calculate and return the maximum of two numbers.
You would like to calculate the maximum among those 512 numbers in the least amount of time.
Each computer can receive two numbers, and return the maximum of those two numbers in 1 second (yeah they’re kinda slow 🐌). Can you think of an algorithm that would allow calculating the maximum of all the given numbers as fast as possible?