Solving the maximum subarray sum: A super-simplified explanation

Python and javascript implementations for algorithms

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 = 6.

What happens when you have a huge array? How do we frame an algorithm to solve this?

The Solution

There are actually many different ways to do this. Let me logically break down two approaches to help you understand the thought process.

Solution 1

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. We just need to consider the consecutive indices as per the question.
• Here are the subarrays- [-1], [-1, 2], [-1, 2, -5], [-1, 2, -5, 7], [2], [2, -5], [2, -5, 7], [-5], [-5, 7], [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]has the maximum sum which is = 7.

Let’s try doing this in two different programming languages. The idea is not just to solve the problem but also to learn the syntax and code of python and javascript. I am assuming you have a basic understanding of how to write code- the for loops, if-else statements, declaring variables, and using functions. If not, do familiarise yourself with these things before you read the code.

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.

Solution 2

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-1 or the max sum till k-1 + kth element 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 -1 and that’s a subarray in itself with sum = -1. Let us assume -1 is part of our target sub-array. -1 is 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 -1 is part of the target array is false. Now, we assume 2 is part of the target array.
• Let us go to the next element, that is -5. -5 is 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, 7 which is greater than the current max sum = 2. 7 + 2 = 9 which is also greater than our current max sum. This means 7 is part of our target subarray and we can update our maximum sum = 9.
• 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.

Here is the code implementation in javascript and python for this approach:

Since we are using only one loop, the time complexity is O(n).

Some observations

• I have run both of these programs in Leetcode for the relevant question (solution 2).
• The javascript program took lesser time to execute than the python code.
• However, python took lesser memory than javascript.

Key Takeaways

• 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.
• If you encounter such a problem in an online test, using javascript over python can help you rank better as it is faster.
• 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

After that, try this problem which isn’t as direct but can be solved using the fundamental logic and thought process we explored here.

Best Time to Buy and Sell Stock - LeetCode