This will be a write up for Leetcode 121 but also a learning process for blogging with Jekyll on github pages.

We are given an array that represent the price of a single stock for 7 days. We don’t have a time machine so we need to buy the stock before we can sell it. Our first example input we have the prices array = [7,1,5,3,6,4] and our expected output is 5. We should get that 5 by buying on the second day at 1 and selling on the fifth day at 6.

This is relatively simple although more complicated than first glance. I started by trying to only maintain the highest value and lowest value, but the timing restriction requires more work than that.

I realized the data we are dependent on is actually our minimum seen price and our currently stored maximum sale price. Our if and else if logic ends up doing a lot of heavy lifting for us in this solution as we actually check our logic conditions perfectly and adjust only when needed, then return the maximum stored value. When done correctly this allows us to set maximum to 0 in the beginning and return that appropriately if a profit is never found and for other corner cases that might arise.

Let’s work through how this code handles the first example input. The first example has prices = [7,1,5,3,6,4] and we are told that is should return 5 as our output. If we think through it you might see that if you buy it at 1 and sell at 6 we get that output. For a person we do a lot of this intuitively with small enough data sets but we need to translate that to how the computer will work through the issue and then we get to scale it.

def maxProfit(self, prices: List[int]) -> int: minimum = prices[0] maximum = 0

for i in range(len(prices)):
    if prices[i] < minimum:
        minimum = prices[i]
    elif prices[i] - minimum > maximum:
        maximum = prices[i] - minimum
return maximum

First Loop Iteration

If we loop through and maintain the local maximum sale and the absolute minimum buy price we would start by looking at the first indices of the array and set maximum = 0 as the buy and sell price are both 7, and we set the minimum = 7 as well, as it’s the minimum we’ve seen. I seed the values of minimum to the first element of the array and I seed the maximum sale price to 0 to handle some of this logic appropriately.

Second Loop Iteration

On our next iteration of our loop we will look at the second element of the array and set minimum = 1, the value of the second element in the array. We actually are done when this happens as we can’t get a new maximum sale on the same day as we get a new absolute minimum, no matter how low the minimum is we don’t have any profit if we buy and sell in the same day.

Third Loop Iteration

In the 3rd iteration of the loop we start again by checking if the minimum is changing. Our minimum will be 1 and our current element will be 5 so we don’t change it. Now we see if our minimum subtracted from the current element value is greater than our maximum. If it is then we have found a new maximum profit and we set our maximum to this new value of 5 - 1 which is equal to 4.

This continues on through the rest of the array. I didn’t start with the code I’ve shared above, I had 3 variables initially and some more logic that I thought was necessary but was able to wrap into the if and elif statements. I had to adjust and retest using all the test cases of Leetcode but mostly was having issues with the corner cases. I’m going to try and consider what corner cases might look like from the outset for future problems.