Today we're going to discuss the optimal solution to the maximum sum subarray problem.
What's the maximum subarray problem?
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]
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]
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]
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]
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]
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)
I understand the brute force solution but don't quite get the idea of the Kadane's algorithm. Could you further explain it?
Given
Ais the array,A[i]is the value of the element at the positioni(zero-based)maxSum(i)is the function that will return the maximum of sum subarray to the positioni. In other words,maxSum(i)is the answer of the problem for smaller input (array of elements from position0to positioni).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 positionimust includeA[i]and themaxSum(i-1)is already the best choice for the previous possible subarray combinations. So eitherA[i]orA[i] + maxSum(i-1)will be the maximum.Cheers
Does this imply recursion? How is this better than the brute force one? Thanks for your reply.
It is but that recursive can be converted to one
forloop since every maxSum(i) will end up calling maxSum(0). Thus if we go from 0 toiand calculate and store the results (or at least the last result) the time complexity of the algorithm will be linearO(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.