Kadane's Algorithm
Track the best running sum ending at each position to find the maximum sum of a contiguous subarray in one pass.
Kadane's Algorithm Practice Problems
Medium
4 problems- 116medium
Maximum Subarray
Find the contiguous subarray with the largest possible sum.
- 117medium
Maximum Product Subarray
Find the contiguous subarray with the largest possible product.
- 268medium
Maximum Sum Circular Subarray
Find the maximum sum of a contiguous subarray in a circular array.
- 269medium
Maximum Absolute Sum of Any Subarray
Find the maximum absolute value of the sum of any contiguous subarray.
Hard
1 problemsHow to practise Kadane
Spotting one
You want the best unbroken run inside a list. Biggest total, biggest product. And the values can be negative.
Unbroken is the important word. If you are allowed to pick and choose items freely, this is not the method.
Kadane or sliding window?
This is the distinction worth getting straight, and the sliding window page covers the other half of it.
Sliding window leans on an assumption: once a stretch goes bad, making it longer cannot rescue it. True when everything is positive. False the moment a negative appears, because a negative can pull a bad total back into a good one. When negatives are in play, Kadane is the tool.
Where to start
Maximum Subarray is the plain form. Everything else here is a variation on it.
Maximum Product Subarray next, and it teaches the most useful lesson on this page. You have to track the smallest running product as well as the largest, because a big negative multiplied by another negative becomes the new winner.
Maximum Sum Circular Subarray adds a tidy trick: the best run that wraps around the end is everything except the worst run in the middle.
Maximum Absolute Sum of Any Subarray and Maximum Subarray Sum with One Deletion build from there.
Common mistakes
Starting the best-so-far at zero. If every number is negative the answer is the least bad single number, and starting at zero reports zero, which is not a run at all.
On the product version, tracking only the maximum and then being surprised when two negatives beat it.
Related concepts
| Topic | Description |
|---|---|
| Prefix Sum | Precompute running totals so the sum of any range can be answered instantly instead of adding it up every time. |
| Sliding Window | Solve fixed-window problems: maximum sum of k elements, moving averages, and O(n) updates as the window slides. |
| Two Pointers | Scan a sorted array or string from both ends at once to find pairs, remove duplicates, or reverse data in O(n). |
| Binary Search | Cut a sorted range in half on every step to find a value or boundary in O(log n) instead of checking one by one. |
| Depth-First Search | Explore as far as possible down one path before backtracking, used to walk trees, graphs, and grids. |
| Breadth-First Search | Explore level by level from a starting point, the go-to way to find the shortest path in an unweighted graph. |