Algorithmically Speaking - #9: Maximum Subarray Sum
Let's explore up to four different solutions to the same problem.
Hello there!
Today we are going to be diving into one of the most classic algorithmic problems we face when learning how to code: the Maximum Subarray Sum problem.
This problem is the perfect excuse for me to introduce you to the Divide & Conquer paradigm and it will serve as a very complete example of how to optimize for memory and time when creating a solution.
At the end of the post, you will find some algorithmic challenges so you can try and apply some of the topics that I will explain today. Feel free to skip to that part if you think you already have the necessary skills to solve them.
Let’s begin!
Formulating the Problem
In its simplest terms, the problem can be formulated as follows:
Given an array of N
integers, find the maximum sum of a subarray.
As an example, let’s say our array is x = [1, -2, 3, 4]
.
The answer in this case is 7
, corresponding to the subarray [3, 4]
.
By definition, a subarray of an array is a contiguous segment of elements that belong to the array. The entire array is considered a subarray also.
For example, if all the elements in the array are non-negative then the answer to the problem is the sum of the entire array.
Examples of subarrays of the array [1, -2, 3, 4]
are:
[1, -2]
[-2, 3, 4]
[4]
Notice also that it can be the case that more than one subarray has the largest sum. We won’t care about this, we will only focus on returning the numeric value of the sum.
Let’s start solving this problem and improve our solution along the way!
Brute Force Solution O(N^3)
The most straightforward solution for this problem is to iterate through every subarray, calculate its sum, and keep track of the largest sum we find.
After we finish this process, we will undoubtedly have the correct answer to return. And if you think about it, it makes perfect sense. We are analyzing every subarray, and one of them has the largest sum. We cannot fail with this approach, it will always be correct.
Here’s a possible implementation of this solution:
Nevertheless, if we were to analyze this algorithm thoroughly we will realize that it takes some time to return the correct answer. These are roughly the operations we do and how much time they take:
We fix the left end
(l)
of a subarray. Time complexity isO(N)
. Then,we fix the right end
(r)
of a subarray. The time complexity for this step is againO(N)
, but since we do it for every possible left end, the time complexity of the whole algorithm until this point isO(N^2)
. Then,we iterate through all the elements in the range
[l, r]
, adding their values to a variable. Once again this is done inO(N)
time, but since we do it for every possible pair of values ofl
andr
, the time complexity of this algorithm ends up beingO(N^3)
.
What does this mean? Well, it means that if the array has N
elements, the algorithm will take approximately N^3
operations to finish. For an array of size N = 1000
, this will mean up to 10^9
operations.
Translated to time, taking into account that the average computer by the time this article is being written can perform around 10^8
operations per second, it means that it would take 10
seconds to find the correct answer. And the worst part is that even if the number 1000
might seem large, it is relatively small for practical purposes.
It has to be better ways to solve this problem. Let’s keep discovering them!
Brute Force Solution O(N^2)
Let’s start with an observation that will allow us to improve the previous solution. It all starts with answering the following question:
Do we need that third for-loop?
We use it to calculate the sum of the elements inside the range [l, r]
once the range has been fixed. But we are not taking advantage of a property that holds through the entire solution:
In the previous formula, sum(l, r) stands for the sum of the subarray [l, r]
, while x[r] is the element at position r
in the array.
This means that if we have already calculated the sum of the subarray [l, r - 1]
, calculating the sum of subarray [l, r]
is just adding the value of x[r]
. It might seem obvious now, but the previous solution was not taking advantage of this observation and was iterating a lot of values without any need.
That being said, we could modify our solution to look like this:
Notice how we only have two nested loops, and we update the value of the variable answer
every time we add a new value to the sum of the current subarray. This minor improvement makes the solution run in O(N^2)
, which is quite great progress.
Let’s see how we can keep improving!
Divide & Conquer Solution O(NlogN)
Disclaimer: If you have seen the Merge Sort algorithm before, the next solution will not come as such a surprise. Otherwise, it will surprise you.
Let’s analyze if we can break the problem into smaller subproblems, solve them recursively and combine their solutions to solve the original problem.
Suppose we want to calculate the maximum subarray sum of the array x[l:r]
, where l
and r
represent the left and right ends. Let’s divide this array into two subarrays x[l:m]
and x[m + 1:r]
, where m
is the middle index.
Let’s say that the x[i:j]
is the subarray with the maximum sum. Then, one of the following conditions must be true. This subarray:
Lies entirely in the left subarray
(l <= i <= j <= m)
.Lies entirely in the right subarray
(m + 1 <= i <= j <= r)
.Crosses the middle index
(l <= i <= m <= j <= r)
.
So, when solving the problem for the subarray x[l:r]
, we can recursively solve the same problem in the subarrays x[l:m]
and x[m+1:r]
, because they are subproblems of the original problem.
Then, we need to calculate the maximum sum of a subarray crossing the middle point. After that, we return the largest of those three values.
The base case of our recursive algorithm is when the subarray we are analyzing is empty or consists of 1 element.
This is a possible implementation of the algorithm we just described:
Finding the maximum crossing sum can be done in O(n)
like this:
I won’t dive deeper into the details of explaining why this solution works in O(NlogN)
, but if you are familiar with Merge Sort you will realize that this algorithm behaves similarly. Their time complexity can be defined by the recurrence relation:
If you are curious enough to read about time complexity, you will find actual proof that this algorithm runs with the time complexity of O(NlogN)
. If you are not, don’t worry, this newsletter will cover those topics in detail very soon.
Now, there is still room for improvement in our algorithm. Let’s keep going!
Kadane’s Algorithm Solution O(N)
Kadane's Algorithm is a dynamic programming solution for solving the Maximum Subarray Sum problem. It solves it in linear time, making it one of the most efficient algorithms.
The algorithm maintains two variables, maxSoFar
, and maxEndingHere
, which are used to keep track of the maximum subarray sum seen so far and the maximum subarray sum that ends at the current index, respectively.
The maxEndingHere
variable is updated by taking the maximum of either the previous maxEndingHere
value plus the current array element or the current array element itself. If this value is greater than maxSoFar
, we update maxSoFar
accordingly.
This process is repeated for each element in the array, resulting in the maximum subarray sum.
One of the key advantages of Kadane's Algorithm is its simplicity and ease of implementation. Unlike other methods, it does not require complex mathematical reasoning or recursive function calls.
It can be easily coded in just a few lines of code, which makes it a popular choice for many programmers.
In terms of time complexity, Kadane's Algorithm has a linear time complexity of O(n)
. This is because it only requires a single pass through the input array. In terms of space complexity, it requires only two variables to be stored, giving it a space complexity of O(1), making it memory efficient.
Here’s a possible implementation of the algorithm:
Time to try what you learned!
Test your Skills
Now that we know how to efficiently solve the Maximum Subarray Sum problem, I will leave you with a challenge you can consider during the week.
We can discuss the answers to this problem as a community and you can share your answers privately by replying to this email.
Here we go:
Problem #1: How can we design a Divide & Conquer solution for finding the maximum element in an array of integer numbers?
Conclusions
I hope I was able to ignite your passion for creating elegant and efficient solutions by driving you through one of the most classic algorithmic problems in the history of Computer Science.
Some takeaways:
Brute Force solutions are generally bad because they take too long to compute the answer for the problem we are solving. Nevertheless, they are often easy to think about and implement. Which solution you want to use depends on your specific use case.
The Divide & Conquer paradigm is often the solution for solving problems that can be broken down into subproblems, and their solutions can be combined somehow. It is very related to the Dynamic Programming paradigm.
Focusing on truly understanding every aspect of the problem you are solving can often lead to implementing very efficient solutions like Kadane’s algorithm. Still, there’s always a trade-off: these solutions often take longer to think about and implement. I will repeat it: use the solution that best suits your needs.
I wish you good luck when solving this week’s challenge. Don’t forget to share your progress with the community!
As always, if you think this post provides value for someone you know, share it with them. Nothing will make me happier.
See you next week,
Alberto