Maximum Subarray with Kadane's Algorithm
Kadane's algorithm tracks the best subarray ending at the current position and the best result seen overall.
What is Maximum Subarray with Kadane's Algorithm?
Kadane's algorithm tracks the best subarray ending at the current position and the best result seen overall.
Find the contiguous subarray with the largest sum in Python.
When should you use it?
- Practice problem solving and data structures.
- Process data when every algorithm step must be explicit.
- Prepare for programming exercises, exams, and interviews.
Example code
main.py
def maximum_subarray_sum(values):
current = best = values[0]
for value in values[1:]:
current = max(value, current + value)
best = max(best, current)
return best
print(maximum_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))Expected output
6How it works
At each value, the algorithm chooses between starting a new subarray and extending the previous one. It runs in O(n) time and O(1) space.
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.