This past month, a few friends and I have been studying and preparing for the AWS Cloud Practioner Cert exam. However, due to the importance of this week in certain world events, my anxiety has been at an all-time high while my productivity has been at an all-time low. With that in mind, I won’t be continuing on my AWS blog series this week. However, I wanted to be SOMEWHAT productive, and I’ve been feeling rusty with my Ruby lately, so I wanted to work on an algorithm from Leetcode in Ruby to brush up on my skills. I ended up working on the Maximum Subarry algorithm, and here is what it looks like:
Basically, I need to return the highest sum of the integers that I can group together inside the array. While we need to keep track of the numbers that we add together, we are only returning a single sum, so that simplifies some things for us.
I want to start by making a variable that tracks our current max value, and one that tracks the highest recorded max value at the end of the chain of the subarray. For example, if the array is [1, 3, -10, -5, 12], the max ending with the last element of [12] will end up being [-5, 12], or 7, so 7 would be our max ending at the chain of -5 and 12 . We’ll set their starting value at the first number inside the nums array.
With these variables in hand, we can then iterate through the nums array and, for each iteration, compare the sum of the new number and our old max. We will then the new number that we added, and the new sum created from adding, and set a new max using the .max method. In the above example, we’ll need to compare the value of the max ending at 12, which would be 7, to the sum of any other combination we tested up to that point. If 7 is the highest number, we will then set that to the new maxSoFar, and return it. We will compare those two numbers with another .max method. Here is what we end up with.
So as we iterate down the length of the array, we are checking the first number, adding the next, and then using the .max method, we are seeing if that number exceeds our highest recorded value.
This was the fastest solution that I could come up with, but am definitely interested in hearing what a faster Ruby solution would be. Good luck this week, and remember to breathe.
