Kadane's Algorithm: Find the Maximum Subarray Sum

By Hourly DSA · October 7, 2026 · 4 min read

Kadane's algorithm finds the largest sum of a nonempty contiguous subarray by deciding, at each position, whether to extend the previous subarray or start again. It needs one scan and two running values: the best sum ending here and the best sum seen anywhere.

The useful insight is knowing which earlier work can still improve the next answer.

Define what counts as a subarray

A subarray contains consecutive elements in their original order. You can choose where it starts and ends, but you cannot skip values in between.

For example:

values = [4, -6, 3, -1, 5, -2]

The maximum-sum subarray is [3, -1, 5], with sum 7. Choosing only 4, 3, and 5 would give a larger total, but those values do not form a contiguous subarray.

We'll require at least one element. That condition matters when every value is negative.

Give the running value a precise meaning

Let endingHere mean the largest sum of a nonempty subarray that ends at the current position.

When the next value x arrives, a subarray ending there has two possibilities:

Start at x, giving sum x.
Extend a subarray ending at the previous position, giving sum endingHere + x.

Among subarrays ending at the previous position, only the largest sum matters. Adding the same x to a smaller sum cannot make it win.

That gives the update:

endingHere = max(x, endingHere + x)

This is a small dynamic programming state: a precise answer to a smaller question, reused to answer the next one.

Trace the extend-or-restart decision

Start both running values at the first element, 4. Then process the remaining elements:

Value	Best sum ending here	Best sum so far
4	4	4
-6	-2	4
3	3	4
-1	2	4
5	7	7
-2	5	7

At 3, extending the previous sum would give -2 + 3 = 1. Starting again gives 3, so the earlier elements are dropped.

At -1, extending gives 2, which is better than starting again at -1. A negative element can belong inside the best subarray: here it connects 3 to the later 5.

The restart decision depends on the previous running sum, not simply on whether the incoming element is negative.

Keep the local answer separate from the overall answer

After the final -2, endingHere is 5. The answer to the whole problem is still 7, found one position earlier.

Returning only endingHere would force the chosen subarray to include the final element. Keep a separate value called best for the largest sum found at any endpoint.

For a nonempty array of length n, the complete scan is:

endingHere = values[0]
best = values[0]
for i from 1 through n - 1:
    endingHere = max(values[i], endingHere + values[i])
    best = max(best, endingHere)
return best

Update endingHere before comparing it with best, so the current position is included in the overall answer.

Don't accidentally allow an empty answer

Consider [-5, -2, -8]. The maximum nonempty subarray is [-2], so the answer is -2.

Initializing best to zero would incorrectly return zero. No nonempty subarray in that input has that sum.

Starting both values at the first element handles all-negative arrays and single-element arrays consistently. If the input may be empty, define that case separately: there is no nonempty subarray to choose.

Some versions explicitly allow the empty subarray, with sum zero. That changes the answer for all-negative inputs. Read the requirement before choosing the initialization.

Explain the cost and the boundary of the pattern

Each element requires a fixed number of additions and comparisons. The algorithm takes O(n) time and O(1) auxiliary space, assuming fixed-cost arithmetic and sums that fit the numeric representation.

These two values return the maximum sum. To return the actual subarray boundaries, also track the current start and save its endpoints whenever you record a better overall sum.

Recognize the basic pattern when the question asks for the largest sum over any nonempty contiguous range. A fixed-length range calls for a different update, such as a sliding window. Counting ranges with a particular sum is another task again.

Check one restart

For [2, -5, 4, 1], what should happen when you reach 4?

Start again at 4. The previous best sum ending at -5 is -3, so extending gives only 1. Including the final 1 then produces the overall answer, 5.

Use Hourly DSA to practice small reasoning steps like this. Before updating a value, say what it represents and which choices are still possible.