Kadane's Algorithm: Complete Guide with Examples

Coding Patterns - Guide to 30 Core Algorithm Patterns

Kadane’s algorithm finds the maximum sum of a contiguous subarray in a single pass over the array. The brute force approach checks every possible start and end index, which costs

O(N^2)

time. Kadane’s algorithm solves the same problem in

O(N)

time with

O(1)

extra space, and it shows up in interviews far more often than the brute force version.

Definition: Kadane’s algorithm is a dynamic programming technique that tracks the best subarray ending at each position. At every element it makes one decision. Either extend the current subarray by adding the element, or drop everything and start a new subarray at that element. Whichever choice is larger becomes the new running total, and a separate variable records the best total seen anywhere so far.

Real-World Analogy

Think of a long hike on a trail with constant ups and downs. You want the stretch of trail with the greatest net gain in elevation, and you are only allowed to walk the trail once, front to back.

You keep two numbers in your head. The first is the running gain since your last restart. The second is the best stretch you have seen so far on the whole hike. At each marker you decide whether to keep climbing or restart. If the running gain goes negative, then the climb so far has cost you more than it earned. Carrying that debt forward can only drag down everything ahead, so you restart your measurement at the current marker instead. If the running gain is still positive, you keep going, because whatever comes next adds on top of a gain rather than a loss.

The trail only gets walked once. That is the whole trick. No backtracking to re-measure earlier sections, no second pass. Just one forward walk with two running numbers.

Visual Explanation

The core of the algorithm is the extend-or-restart decision at every position.

    graph TD
    I["max_ending_here = max_so_far = nums[0]"] --> C{"i < n?"}
    C -->|Yes| D["Compare nums[i] vs max_ending_here + nums[i]"]
    D -->|"restart wins"| E["max_ending_here = nums[i]"]
    D -->|"extend wins"| F["max_ending_here += nums[i]"]
    E --> G["max_so_far = max(max_so_far, max_ending_here)"]
    F --> G
    G --> C
    C -->|No| H["return max_so_far"]

Here is the algorithm tracing through the classic example [-2, 1, -3, 4, -1, 2, 1, -5, 4]. The best subarray is [4, -1, 2, 1], which sums to 6.

i	nums[i]	max_ending_here	max_so_far
0	-2	-2	-2
1	1	1	1
2	-3	-2	1
3	4	4	4
4	-1	3	4
5	2	5	5
6	1	6	6
7	-5	1	6
8	4	5	6

Two things are worth noticing in this trace. At index 3, the running total restarts at 4 because 4 beats -2 + 4. From then on the running total extends through index 6, reaches 6, and never beats that again. The answer is recorded the moment it is reached, not at the end of the array. That is why the algorithm needs two variables instead of one.

When to Use This Pattern

Use Kadane’s algorithm when the problem has these characteristics.

You need the maximum (or minimum) sum of a contiguous segment of an array. Words like “subarray” or “contiguous” are the signal.
The array contains negative numbers. With only positive numbers the answer is the whole array, and with a sliding window you would shrink from the left. Negative values are what make the extend-or-restart decision meaningful.
The problem asks for a maximum profit or best window that can be rewritten as a maximum subarray. Stock profit problems reduce to Kadane’s algorithm by taking the differences between consecutive prices.
The brute force checks every start and end pair, and the constraints make
O(N^2)
too slow. A single pass is the tell.
A circular array is involved. The wrap-around case uses Kadane’s algorithm twice, once for the maximum and once for the minimum.

Complexity Analysis

Aspect	Complexity	Explanation
Time	O(N)	Each element is visited exactly once, with constant work per element
Space	O(1)	Two running variables regardless of input size

The time is

O(N)

because the algorithm makes one pass and never revisits an element. The decision at each position compares two candidate values and does one comparison, so the per-element work is constant.

The space is

O(1)

because the state only needs two integers. The best subarray ending at position i depends only on the best subarray ending at position i-1. Nothing earlier is ever needed again, so the full DP table collapses into a single rolling variable. This is the same space optimization that shows up across many 1D dynamic programming problems.

Memorizing complexity tradeoffs is half the battle. The other half is remembering them under pressure. Review this pattern with spaced repetition so the analysis becomes automatic by interview day.

Common Mistakes

These bugs all share one root cause. The extend-or-restart decision is slightly different from what intuition expects, and the failure only shows up on specific inputs.

Initializing the accumulators to 0. If every element is negative, starting max_ending_here at 0 produces 0 as the answer. That would mean an empty subarray, which is not allowed. Initialize both accumulators to nums[0] and start the loop at index 1. Trace [-3, -1, -2] on paper before coding. The correct answer is -1.

Updating max_so_far before max_ending_here. The global best must be compared against the new running total. Reversing the order compares against the previous position’s value, which misses any improvement at the current position. Keep the two-line sequence intact. First compute the new running total, then compare.

Returning max_ending_here instead of max_so_far. The running total at the last element is the best subarray ending at the last element. The best subarray overall may end anywhere. On [-2, 1, -3, 4, -1, 2, 1, -5, 4] the running total at the end is 5 but the answer is 6, which was reached two positions earlier.

Confusing Kadane with sliding window. In a sliding window, a window with a bad sum shrinks from the left until the condition holds again. Kadane has no window. A negative running total is discarded entirely and the next element starts fresh. Trying to maintain a left pointer and a window size here overcomplicates the code and often introduces off-by-one bugs.

These mistakes are expensive because they look correct until they fail on a hidden test case. Our review decks flag exactly these edge cases and drill them until they are reflex. Add this pattern to your queue .

Related Patterns

Dynamic Programming . Kadane’s algorithm is the space-optimized form of a 1D DP recurrence. The array manipulation page covers it as a running-accumulator technique, and the DP page covers the broader family of state-transition problems.
Prefix Sum . Prefix sums answer many range-sum queries in
O(1)
time after
O(N)
preprocessing. Kadane answers a different question, the best single subarray. When a problem asks for many subarray sums, prefix sum is the tool. When it asks for one optimal subarray, Kadane is.
Sliding Window . Sliding window also processes arrays in one pass, but it maintains a bounded window and shrinks from the left. Kadane’s restart is the right move when the running sum goes negative, which is exactly the case where a sliding window gets stuck.

Next Steps

Once the decision rule is clear, the next step is making the code automatic. Check out the code templates for memorizable implementations in 6 languages, then work through the practice problems to apply the pattern to real interview questions.

Reading about a pattern once is not enough to own it in an interview. Practice this pattern with spaced repetition and turn recognition into recall.