Introduction

Kadane's algorithm is often presented as a clever running-sum trick, but its real foundation is dynamic programming. At each position, it solves a tiny subproblem: what is the maximum subarray sum that ends exactly here? Once you see that recurrence, the algorithm becomes much easier to reason about and to modify.

The Dynamic Programming Recurrence

Suppose best_end[i] means the maximum subarray sum that must end at index i. Then there are only two possibilities for the best subarray ending at i:

• start fresh with arr[i]
• extend the best subarray ending at i - 1

That gives the recurrence:

best_end[i] = max(arr[i], arr[i] + best_end[i - 1])

The global answer is then the maximum value of best_end[i] over the whole array.

This is classic dynamic programming:

• the problem has optimal substructure
• each state depends on the previous state
• you can compute the answer in one pass

A DP Array Version

Writing it with an explicit DP array makes the idea obvious.

1def max_subarray_dp(arr):
2    best_end = [0] * len(arr)
3    best_end[0] = arr[0]
4    best_total = arr[0]
5
6    for i in range(1, len(arr)):
7        best_end[i] = max(arr[i], arr[i] + best_end[i - 1])
8        best_total = max(best_total, best_end[i])
9
10    return best_total
11
12
13print(max_subarray_dp([4, -1, 2, 1, -5, 4]))

This prints 6, because the best subarray is [4, -1, 2, 1].

The DP array is useful for learning and debugging, because you can inspect the value of every subproblem.

Why Kadane's Algorithm Uses Only Two Variables

Once you notice that best_end[i] depends only on best_end[i - 1], the full DP array becomes unnecessary. You can keep only the current state and the best answer seen so far.

1def kadane(arr):
2    current_max = arr[0]
3    global_max = arr[0]
4
5    for value in arr[1:]:
6        current_max = max(value, current_max + value)
7        global_max = max(global_max, current_max)
8
9    return global_max
10
11
12print(kadane([4, -1, 2, 1, -5, 4]))

This is still dynamic programming. It is just the space-optimized form of the same recurrence.

That is the key point people sometimes miss: Kadane's algorithm is not a different idea from DP. It is DP compressed into constant memory.

Recovering The Actual Subarray

The basic algorithm gives only the sum, but you can extend it to track the start and end indices.

1def kadane_with_indices(arr):
2    current_max = arr[0]
3    global_max = arr[0]
4    start = end = temp_start = 0
5
6    for i in range(1, len(arr)):
7        if arr[i] > current_max + arr[i]:
8            current_max = arr[i]
9            temp_start = i
10        else:
11            current_max = current_max + arr[i]
12
13        if current_max > global_max:
14            global_max = current_max
15            start = temp_start
16            end = i
17
18    return global_max, start, end
19
20
21print(kadane_with_indices([4, -1, 2, 1, -5, 4]))

This is another reason the DP viewpoint helps. Once you understand the state transition, extending the algorithm becomes straightforward.

Common Pitfalls

The most common mistake is initializing the running sums to 0. That breaks the all-negative case, because the correct answer for [-4, -2, -7] is -2, not 0.

Another issue is treating Kadane's algorithm as a magic rule without understanding the recurrence. That makes it harder to adapt the algorithm for related problems such as tracking indices or adding constraints.

It is also easy to forget the distinction between current_max, which is the best subarray ending at the current position, and global_max, which is the best seen anywhere so far.

Finally, the standard form solves the non-empty maximum subarray problem. If your specification allows an empty subarray with sum 0, the initialization rules change.

Summary

• Kadane's algorithm is a dynamic programming solution to the maximum subarray problem.
• The core recurrence is max(arr[i], arr[i] + best_end[i - 1]).
• The usual two-variable implementation is just the space-optimized form of that DP.
• Understanding the DP state makes it easier to recover indices or extend the algorithm.
• Initialize carefully so arrays containing only negative numbers are handled correctly.