Leetcode 53: Maximum SubArray Sum
One of the Leetcode problems that I worked on this week is called Maximum Subarray Sum. If you would like to try it yourself, you can find it here. Although this is a relatively simple problem, I learned something new about JavaScript in the process of solving it, which is always great. I’m going to do a brief walkthrough of the problem and my solution, and I hope that it helps anyone who may be stuck.
The Problem
Write a function that takes an array as an argument. This function should find the subarray with the greatest sum, and return that sum. For example, if the array was [ 1,- 5, 4, 5 ], the function would return 9, since [4,5] is the subarray with the greatest sum. Also, it is important to note that if all of the numbers in the array are positive, the entire array will be the subarray with the greatest sum.
My Approach
I had a fairly solid idea of how I wanted to approach this problem going into it. I decided to create two variables and set them to 0. One of these variables would serve to keep track of the current total of array values, and the other would store the highest total by comparing itself to the current total. Then, I would loop through the array and add the value at each index to the current total. If the current total was greater than the highest total, the highest total would become the current total. This seemed relatively straightforward, but I hit an unexpected bug. Below, you can see my original solution before I refactored it.
The function above passed the initial handful of test cases, but when I tried to submit it, I hit a failed test case. The issue was that the function above has no way of dealing with negative numbers. This is a huge issue, since negative numbers are very important to this problem. If all of the numbers were positive, there would be no point to calculating the highest subarray sum, since it would just be the sum of the entire array.
The cool thing that I learned
I have a lot to learn about the JavaScript’s built in Math Object. There are a ton of cool methods that are built into the Math object, and I have only used a handful of them. In order to solve my problem, I needed my max variable to initialize as the lowest possible number, so that any negative number in the array would still be greater than it. enter Number.MAX_VALUE. Thankfully, as always MDN had a great explanation for me. Number.MAX_VALUE represents the greatest possible value of a number in JavaScript. So, I needed to use a negative version of it to solve my problem. Thankfully, that simple change was all I needed! See my updated solution below.
I think Number.MAX_VALUE will come in handy in a ton of problems I solve, whether it be positive or negative. Thank you for reading, and I hope that this article taught you something new!
