Why Kadane's algorithm works?
Jun 24, 2018
Kadane’s Algorithm, aka Maximum Sum of Subarray, is an interesting algorithm problem that can be solved with different approaches. This problem is a nice and intuitive question to learn more about Dynamic Programming.
Maximum Subarray Problem
In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array, a[1…n], of numbers which has the largest sum.
The task is to find a subarray (contiguous elements) of the given array that has the largest sum. For instance:
[1, 5, -1, 0, 10]
The answer would be
15 or the entire array (it’s also a subarray)
[0, -1, -5, 0, -4]
The answer would be
0 and so on.
We are going to explore two solutions to attack this problem: Brute-force and Dynamic Programming.
Using brute-force to solve this problem is trivial. All you need is going through all sub-arrays, keep the global maximum and compare.
But I don’t think this is a clever answer. Or more broadly, brute force is not a clever answer most of the times.
Dynamic Programming (Kadane’s Algorithm)
Kadane’s algorithm is the answer to solve the problem with
O(n) runtime complexity and
Following function shows the Kadane’s algorithm implementation which uses two variables, one to store the local maximum and the other to keep track of the global maximum:
def max_subarray(A): max_ending_here = max_so_far = A for x in A[1:]: max_ending_here = max(x, max_ending_here + x) max_so_far = max(max_so_far, max_ending_here) return max_so_far
So we assume that the largest subarray is the first element, then we go through
A[1:] elements (all elements except the first one).
At each step, what we do is:
- Can current element plus the last largest sum_ help to find a largest subarray (line 4)?
- If yes, update the
max_ending_hereor our local maximum, otherwise current element is the largest subarray (array of one).
- Then update the global maximum or
max_so_farif there is a new global maximum.
When the loop is over, return the global maximum.
But that might be a bit unintuitive to grasp why
max_ending_here is calculated. I rewrote that script this way:
def max_subarray(A): max_so_far = A elements_so_far = [A] for x in A[1:]: if x > sum(elements_so_far + [x]): elements_so_far = [x] else: elements_so_far.append(x) max_so_far = max(max_so_far, sum(elements_so_far)) return max_so_far
The difference now is, instead of keeping a sum of contiguous elements we keep the actual elements such that:
- Assume the first item of our array is the maximum, so add it to
- Go through all elements except the first one
- Is the current element bigger that the sum of entire elements that we’ve seen? (i.e
- If yes, reset the
elements_so_farto this element, otherwise just keep adding items
I hope it makes a bit more sense now. Be aware that adding that array can increase the space complexity by O(n).
Kadane’s algorithm is a Dynamic Programming approach to solve “the largest contiguous elements in an array” with runtime of O(n). In this blog post we rewrote the algorithm to use an array instead of sum (which needs more space to hold them) that makes it a bit more easier to understand.
← Back to all articles