Leetcode 53: Maximum SubArray Sum
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.
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 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!