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

How to Enrich an Input Lead with Additional Data Fields in Javascript

Livewire — An Easy Way To Build Dynamic Web Applications (Part 1)

Contux — Flux like State Management using enhanced components on top of the new React Context API

Tree-shaking ES6 Modules in webpack 2

React Conf 2021 — React Forget

A-Frame — AR.js

Build and Deploy a GraphQL API to AWS with Serverless

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

CS373 Spring 2022: Yifan Zhou

CS371p Spring 2022: Winnie Chang

Collaborative Coding Best Practices Implementation in My Project

LeetCode 143. Reorder List

exampleOne