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.

My nearly correct first attempt

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!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

test this medium post

A simple introduction to JavaScript closure in 2 minutes

Reverse Stack using Recursion

React simple polling custom hook usePollingEffect.

Managing your react state with unstated

How to compress files to create a new zip archive in Node.JS

Maximum Number of vowels in a substring of given Length.

Part 1: The JavaScript OLOO Pattern Explained (with pictures)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Liam Hanafee-Areces

Liam Hanafee-Areces

More from Medium

How to Avoid Falling for the Couponing Scam

Comparison between Selection Sort and Insertion Sort

FORESIGHT 2021 | Software Development Engineer at Cisco | Vineeth

The Best SWE Interview Question