Clean Code Studio
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!
