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

From Wikipedia:

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 [10].

[0, -1, -5, 0, -4]

The answer would be [0] and so on.

Solutions

We are going to explore two solutions to attack this problem: Brute-force and Dynamic Programming.

Brute-force

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 O(1) space.

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[0]
    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_here or our local maximum, otherwise current element is the largest subarray (array of one).
  • Then update the global maximum or max_so_far if there is a new global maximum.

When the loop is over, return the global maximum.