I am writing this post as I could not find any reliable material that could clearly explain the intuition behind Kadane’s algorithm.
To start, here’s a (very) crisp explanation of Kadane’s algorithm from Wikipedia.
Kadane’s algorithm begins with a simple inductive question: if we know the maximum subarray sum ending at position
(call this
), what is the maximum subarray sum ending at position
(equivalently, what is
? The answer turns out to be relatively straightforward: either the maximum subarray sum ending at position
includes the maximum subarray sum ending at position
as a prefix, or it doesn’t (equivalently
, where
is the element at index
Unfortunately, when you see this explanation, it is hard to convince yourself why the algorithm works, but once I prove it to you, then it’ll seem trivial. Here is my attempt to make this explanation more easy to digest.
Q: Does this algorithm cover all subarrays?
Answering the above question is quite simple. It all depends on how you traverse over all the possible subarrays.
Generally, when you ask a programmer to iterate over all the subarrays, they’ll probably write something like this.
for (int i = 0; i < n; ++i) { for (int j = i; j < n; ++j) { // Do something with subarray [i, j] // OBSERVE: All subarrays start with index `i` } }
Another not so uncommon way of iterating is to use as a termination condition in the inner loop, like so
for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { // Do something with subarray [j, i] // OBSERVE: All subarrays end with index `i` } }
Just to drive this concept home, let’s visualise this as a table. Each cell is a subarray (i.e. one iteration of the inner loop), and each row is one iteration of the outer loop.

Table-1: All possible subarrays of an array
- Row number
in
indicates the ending index
for the subarray
- Column number
in
indicates the starting index
for the subarray
From now on, if I refer to a row in the table, then I refer to all the subarrays in the
row and notice that all their ending index is
.
Q: How does knowing the maximum subarray sum of row help us derive the maximum subarray sum of row
.
From the table, we know that the (the maximum subarray sum ending at 0) is nothing but the first element of the array. So, if we can somehow intelligently calculate the
by using
, then finding
becomes a
operation.
The maximum subarray sum of row can be mathematically represented as
If we consider the sum of all elements from index to
as
, we can rewrite the above equation as
If you look carefully in the table, all the subarrays but the last one in the row are nothing but subarrays found in
row with an extra element
slapped on at the end of each subarray. Oh, and the last subarray is a singleton array
.
Another not so common property of that I’d like you to think about is
.
By using the above property, we can replace in the previous equation with
to get
So with just high school mathematics, we’ve proved the induction.
Thanks for the great explanation!
LikeLike