Solving the maximum subarray sum: A super-simplified explanation
The Problem Statement
You have an array of n numbers. You have to find out the largest sum of the consecutive numbers of the array.
That’s essentially finding the subarray which has the largest sum.
For example, an array
[1, 2, 3, 4] will have the largest sum =
10 which is the sum of the array as a whole. For arrays with no negative integers, the maximum subarray sum is the sum of the array in itself.
Now, what happens when you have negative integers?
Take an array
[-1, -3, 4, 2] where the subarray with maximum sum would be
[4, 2] with a sum =
What happens when you have a huge array? How do we frame an algorithm to solve this?
There are actually many different ways to do this. Let me logically break down two approaches to help you understand the thought process.
A very direct approach we can think of can go like this:
- We create all the subarrays possible from the main array.
- We then check the sum of each subarray and return the maximum sum.
Pretty straightforward? Let’s do a dry run to understand this better.
- Let the array be
[-1, 2, -5, 7]
- To create all subarrays of this array, we can pick each element and make a subarray with all other elements in the sequence.
- Here are the subarrays-
[-1], [-1, 2], [-1, -5], [-1, 7], [-1, 2, -5], [-1, 2, 7], [-1, -5, 7], [-1, 2, -5, 7], , [2, -5], [2, 7], [2, -5, 7], [-5], [-5, 7], .Ah, very tedious process.
- With each subarray we make, we can check the sum and keep a record of it.
- Whenever the sum is higher than our previous record, we update the value.
- Once we iterate through all the subarrays, the sum we have recorded will be the required answer.
- If we look at all the subarrays, we notice that
[7, 2]has the maximum sum which is =
We have too many for loops, meaning time complexity is bad. In this case, it is O(n³) because we have three loops to run.
To make things efficient in these kinds of problems we need to think of ways to reduce the number of loops.
Is there a way to solve this with a single loop?
There must be some trick we can use to do it. Let’s see if we can construct a thought process.
- If we are looping through the array only one time, it means we are visiting each element of the array once.
- Let us now connect the dots backward. To find our answer, we need to first find the subarray that will have the maximum sum.
- We definitely need to visit each element once. What can you tell about that element w.r.t to the subarray with maximum sum? It either belongs to that subarray or does not. Right?
- If it does belong to the sub-array with the maximum sum, you can add its value to a temporary variable where you store and keep updating the potential maximum sum. If it is not, you can simply ignore it and move to the next element.
- If you do this across the entire array, what do you get? The sum of all elements that belong to the subarray that has the maximum sum = the answer we are looking for, and we get it by running just one loop!
- Now the question you will have is, how do we know that a given element belongs to that subarray?
- Let us assume an array of n elements. We are at the kth element of this array.
- If this kth element is part of our maximum subarray, what will be special about it? It will either be greater than the sum of elements till
k-1or the max sum till
kthelement will be greater.
- Can you notice how we are creating a subproblem with our logic?
- The maximum subarray sum for this array ending at kth element is effectively the maximum subarray sum of the array till k-1th element + the kth element (if the kth element is positive).
- At any instant of time, we are finding the maximum subarray sum for an array up to the kth element. When we reach the nth element, we would have found the answer for the full array.
Sounds confusing? It’s ok. If this is your first time coming across such a problem it can be a bit complex. Let’s do a dry run with a real array.
- Let the array be
[-1, 2, -5, 7]as in the example we used in solution 1. So, we need to assemble a sum of elements that belong to the sub-array with the maximum sum (let us call it our target sub-array).
- We are running only one loop. So, first, we go to
-1and that’s a subarray in itself with sum =
-1. Let us assume
-1is part of our target sub-array.
-1is now our temporary maximum sum.
- Next, we go to
2. Now, it is either part of our target sub-array or not. How do we know that? If it is part of the sub-array, it should either be greater than the current max sum or be added to the maximum sum.
2 > -1 + 2 = 1, which is greater than our current temporary maximum sum. So, let us update our temporary max sum =
2. This just confirms that our previous assumption that
-1is part of the target array is false. Now, we assume
2is part of the target array.
- Let us go to the next element, that is
-5is clearly lesser than the current maximum sum we have. So, we can ignore it and go to the next element.
- Now, let us go to the next element,
7which is greater than the current max sum =
7 + 2 = 9which is also greater than our current max sum. This means
7is part of our target subarray and we can update our maximum sum =
- We have reached the end of the array and the solution we arrived at is
9, which is the required answer and we just used one loop!
In short, we went to each element of the array and checked if it will be part of the sub-array with the maximum sum. If it is so, we are just adding it to our maxSum variable and moving on to the next element.
At the end of it, we will have the required answer.
Since we are using only one loop, the time complexity is O(n).
- I have run both of these programs in Leetcode for the relevant question (solution 2).
- If you get a similar problem in your interview, do consider thinking out loud about how you are trying to reach a solution.
- Take up a sample test case and do a dry run like I have done here first.
- And after that, you can code it.
- When you are dealing with arrays and notice that you have to iterate through the array, you should think about using the least number of for loops.
- From there, think about what you can do, how you can keep track of useful information as you traverse through each element of the array.
- In these kinds of problems we generally would want to track two variables, the current value which we calculate at each iteration, and the max or min value, which will be the final answer which is continuously updated as we traverse the array.
Fundamental Approach: A summary.1. Have a single for loop.
2. Calculate a currentValue for each element in the array based on the question.
3. Then update the maxValue as max(maxValue, currentValue)
4. Vice-versa for minValue.
Try to solve this Leetcode question by yourself without seeing any references after reading this article, and test your understanding.
Maximum Subarray - LeetCode
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum…
After that, try this problem which isn’t as direct but can be solved using the fundamental logic and thought process we explored here.