Solving Maximum Subarray
Intro:
This blog will be about solving the LeetCode problem #53. Maximum Subarray. Note that this problem will be solved in JavaScript!
The question is asking us to find the elements that are contiguous that add up to the max sum and then return the max sum. The examples do a great job at explaining what the input and output should be and why. There are many ways to solve this problem, I was able to solve this problem with a time complexity of O(n). Please feel free to reach out or leave a comment on this blog if there are better solutions for this problem!
Because we have to return the largest sum from a contiguous subarray, I created a variable that represents the large sum and set that equal to the first element of the nums array. This is what my code looks like at this moment:
The next step is to iterate over the nums array to check for each element. For this step, I will be using a for loop statement!
When creating a for loop statement, the variable i would be set to zero, but in this case we will start from one. Starting from one means that the iteration would start on the first index not the zeroth index. If we have an array [1,2,3,4], that means that the for loop would start at 2 instead of 1.
Now that the logic for the for loop is written, we need to think about what’s supposed to go on inside of this for loop. Based on the prompt and the examples, we need to think about how we’re going to get the largest sum when adding up the elements inside the array. I believe we can get that number by using the current number being iterated on the nums array and the variable that I created largeSum. The current number (nums[i]) being iterated inside the nums array should be equal to the maximum number between nums[i] and the sum of nums[i] plus the previous number. I know that sounded complex, but here’s how the code should look like at the moment:
Let’s say we have an array [1,2,-5,4], the code on line 6 is stating that nums[i] should be equal to the largest number between 2 and 2 + 1. The largest number between the two is three! On the next loop cycle, the next number is now -5 and nums[i] will now be the max number between -5 and -5 + 3 which is -2.
The last step is changing the value of largeSum and then return it after the for loop ends. largestSum needs to be able to keep track of the highest number which is why I decided to use Math.max(). Here’s the solution of the problem and the expected outputs for the LeetCode examples:
It’s always best practice to use different test cases to ensure that the solution is working properly! For more info on the Math library, and for loop statements, make sure to check out the links below!
