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
[0, -1, -5, 0, -4]
The answer would be
 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 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.