The Research Nest
Published in

The Research Nest

Solving the maximum subarray sum: A super-simplified explanation

Python and javascript implementations for algorithms

The Problem Statement

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

The Solution

Solution 1

  • We create all the subarrays possible from the main array.
  • We then check the sum of each subarray and return the maximum sum.
  • 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], [2, -5], [2, 7], [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, 2]has the maximum sum which is = 9.

Solution 2

Is there a way to solve this with a single loop?

  • 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.
  • 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.

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.