Challenge: maximum subarray
Find the largest sum of any contiguous slice — the classic Kadane's algorithm.
- Turn an O(n²) scan of all subarrays into a single pass
- Carry a running best that resets when it stops helping
Optional challenge. The efficiency check counts list reads, so brute force is rejected deterministically — no timing.
Given a list of numbers (which may be negative), find the largest sum of any
contiguous subarray. For [-2, 1, -3, 4, -1, 2, 1, -5, 4] the answer is 6
(the slice [4, -1, 2, 1]).
Checking every possible subarray is O(n²). The elegant solution — Kadane's algorithm — is one pass and a genuine "aha."
Idea: sweep left to right, keeping the best sum of a subarray ending at the current element. At each step that running sum is either "extend the previous one" or "start fresh here" — whichever is larger. Track the best you've ever seen. The insight: a running total that's gone negative can only hurt what follows, so drop it.
Write max_subarray_sum(nums) returning the largest sum of any contiguous (non-empty) subarray. Assume nums is non-empty. Aim for O(n).
max_subarray_sum([-2,1,-3,4,-1,2,1,-5,4]) → 6max_subarray_sum([-1,-2,-3]) → -1The all-negative case is the trap: the answer is the least-bad single element, so your running sum must be allowed to be a single element rather than forced to include earlier negatives.