Smaller subproblems

Independent subproblems / invariant.

Try this in Python

def max_in(a):
    return max(a) if len(a) <= 2 else max(max_in(a[: len(a) // 2]), max_in(a[len(a) // 2 :]))

print(max_in([3, 1, 4, 1, 5]))

Key takeaways

• Merge correctness proof.
• Value vs index split.
• Python stack limits.