Split the list in two
Find the biggest value by finding the biggest of each half and keeping the larger. About 11 minutes.
Two smaller problems
To find the biggest of 8 values, find the biggest of the first four, find the biggest of the last four, and keep the larger. Those two smaller questions are the same question on shorter ranges, so hand them to the same function.
A range is described by its first and last position. Keep splitting until a range has just one value, which is its own biggest. Then the answers combine on the way back up.
def best(lo, hi):
if lo == hi:
return nums[lo]
mid = (lo + hi) // 2
left = best(lo, mid)
right = best(mid + 1, hi)
return max(left, right)The whole range 0 to 3. Split into 0 to 1 and 2 to 3.
Don't forget the empty list
A list with no values has no biggest value. The problem usually promises at least one, but when it doesn't, the question needs an agreed answer before any recursion starts.
Notice the split gives two ranges that together cover every position exactly once: lo to mid, and mid + 1 to hi. If you overlap or skip a position, the answer is wrong, or the calls never end.
A range covers positions 4 to 9. Where do you split it?
- AInto 4 to 6 and 7 to 9
- BInto 4 to 5 and 6 to 9
- CInto 4 to 6 and 6 to 9
Show the answer
Into 4 to 6 and 7 to 9. The middle is (4 + 9) divided by 2, rounded down, which is 6. The second half starts at 7.
Biggest by halves
nums is a list of whole numbers with at least one value. Return its biggest value, using a recursive function that splits the list into a left half and a right half.
nums = [3, 9, 4, 7] → 9
1 ≤ length ≤ 100,000 · −1,000,000,000 ≤ value ≤ 1,000,000,000