DEV Community

Cover image for Kadane's Algorithm (Maximum Sum Subarray Problem)
Clean Code Studio
Clean Code Studio

Posted on • Updated on

Kadane's Algorithm (Maximum Sum Subarray Problem)

Twitter Follow

Today we're going to discuss the optimal solution to the maximum sum subarray problem.


What's the maximum subarray problem?


Maximum Sum Sub-array example


Let's say we have an array that looks like this:
[1, -3, 2, 1, -1]

Sub-arrays are defined as continuous elements.

Note: The entire array is considered a sub-array since all elements are continuous.

[1] = 1
[1, -3] = -2
[1, -3, 2] = 0
[-3, 2, 1] = 0
[1, -3, 2, 1] = 1
[1, -3, 2, 1, -1] = 0
[-3, 2, 1, -1] = -1
[-3, 2, 1] = 0
[2, 1, -1] = 2
[1, -1] = 0
[2, 1] = 3
[1] = 1
etc...

Our maximum sub-array is [2, 1] which sums to 3.


So, how do we programmatically solve this coding challenge?


Brute Force Solution


Basically, we check all of the possible arrays and pick the one with the maximum some.

We'd start at the first index and then move on to the second index and so on - we kinda did that above when we did this.

[1] = 1
[1, -3] = -2
[1, -3, 2] = 0
[-3, 2, 1] = 0
[1, -3, 2, 1] = 1
[1, -3, 2, 1, -1] = 0
[-3, 2, 1, -1] = -1
[-3, 2, 1] = 0
[2, 1, -1] = 2
[1, -1] = 0
[2, 1] = 3
[1] = 1
etc...


Kadane's Algorithm (The Optimal Solution)


The idea is very simple. We're going to look at each index and ask ourselves - what's the maximum sub-array ending at this index?

[1, -3, 2, 1, -1]

Starting at index 0, we have [1].

What's the maximum subarray ending at this index (this currently being 0)?

It's obviously just 1.

Index 0: [1]
Enter fullscreen mode Exit fullscreen mode

For the second index, we're going to ask what the maximum sub-array ending at this index.

At this index, the maximum sum can be [1, -3] or just [-3].

The maximum one of those is [1, -3]

Index 0: [1]
Index 1: [1, -3]
Enter fullscreen mode Exit fullscreen mode

For the third index we'll do the same thing.

The subarray with the maximum sum ending at this index could be.

[2]
[-3, 2]
[1, -3, 2]

The answer is [2]

Index 0: [1]
Index 1: [1, -3]
Index 2: [2]
Enter fullscreen mode Exit fullscreen mode

We just continue using this pattern all the way through, and then compare the remaining subarrays that we have gotten by getting the maximum subarray at each index.

Index 3 has the following subarrays.

We choose [1] or [1, 2] or [1, 2, -3] or [1, 2 -3, 1]

Since 1 + 2 is the highest sum out of all of index three's subarrays we'll use that for index 3.

Index 4 has the following subarrays
[-1] or [-1, 1] or [-1, 1, 2] or [-1, 1, 2, -3] or [1, -3, 2, 1, -1]

Since [-1, 1, 2] has the highest sum index 4 will use that subarray.

The max sub-array at each index.

Index 0: [1]
Index 1: [1, -3]
Index 2: [2]
Index 3: [1, 2]
Index 4: [-1, 1, 2]
Enter fullscreen mode Exit fullscreen mode

Finally, we simply compare the sub-arrays that we have collected at each index and return the one with the highest sum.

[1] or [1, -3] or [2] or [1, 2] or [-1, 1, 2]

Since [1, 2] sums up to 3 and is the highest sum we return [1, 2] as our final value.


As you can see, the idea here is simple - but it's not very efficient. It's going to take O(n^2) time complexity (AKA quadratic time).

But, the interesting idea from Kadane's algorithm is we can do much better than that. We can run it in O(n) time complexity (AKA linear time).

So let's see how we can do this.

Let's say we're using the same strategy here. We begin by finding the max sub-array at each given index.

Now, let's assume we've already resolved the max sub-arrays from our first and second index. We're on index three.

Max sum sub-arrays from index one and two

Index 0: [1]
Index 1: [1, -3]
Enter fullscreen mode Exit fullscreen mode

Original Array: [1, -3, 2, 1, -1]

The next element we have is 2.

Kadane's algorithm states that the maximum sub-array for this index will either be the current element (in this case 2) OR the current element + the previous maximum sub-array.

Example:
To determine the local maximum subarray we were doing the following.

[2] or [2, -3] or [2, -3, 1]

BUT kardane's algorithm states that our local maximum subarray is either the current element OR the current element + the previous maximum sub-array.

Following this principle we can simplify

[2] or [2, -3] or [2, -3, 1]

to

[2] or [2, 1, -3]

We can just compare these, and ignore all other local sub-arrays and this will give us our local maximum sub-array.

This solution is much faster than the brute force algorithm and runs in linear time [aka O(n)].


My personal FAANG interview Notes


Subscribe to the Clean Code Studio newsletter for more!

Top comments (5)

Collapse
 
blackr1234 profile image
blackr1234

I understand the brute force solution but don't quite get the idea of the Kadane's algorithm. Could you further explain it?

Collapse
 
maixuanhan profile image
Han Mai

Given A is the array, A[i] is the value of the element at the position i (zero-based)
maxSum(i) is the function that will return the maximum of sum subarray to the position i. In other words, maxSum(i) is the answer of the problem for smaller input (array of elements from position 0 to position i).

  • maxSum(0) = A[0] since there is only 1 sub array (with at least 1 element).
  • maxSum(i) = Max(A[i], A[i] + maxSum(i-1)) makes sense because a subarray to position i must include A[i] and the maxSum(i-1) is already the best choice for the previous possible subarray combinations. So either A[i] or A[i] + maxSum(i-1) will be the maximum.

Cheers

Collapse
 
blackr1234 profile image
blackr1234

Does this imply recursion? How is this better than the brute force one? Thanks for your reply.

Thread Thread
 
maixuanhan profile image
Han Mai

It is but that recursive can be converted to one for loop since every maxSum(i) will end up calling maxSum(0). Thus if we go from 0 to i and calculate and store the results (or at least the last result) the time complexity of the algorithm will be linear O(n). Brute force on the other hand, we have to find all the subarray and calculate the sum for each and then find the max of the results.

Collapse
 
cleancodestudio profile image
Clean Code Studio