Here's today's problem.
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Thinking of the brute force solution, we'll need to consider all possible transactions and again, this means a bottom-up approach would work better.
Really, I just choose questions randomly which I thought would be fun and they all seem to be coincidentally better for a bottom-up approach, but if anyone knows a question where a top-down approach will work better, feel free to leave a response of the problem and I'll attempt the question as a future post.
Initial Thoughts
Sometimes, the structure of how we should tabulate is not as clear at first. A way to gain some insight into this is to first ask yourself, "Is it possible to solve this in linear time (i.e., O(n))?" If yes, then you're in luck because chances are you'll just need to work with a simple 1D array, otherwise a more complex structure is often needed.
So in this question, do you think it's possible to solve this in linear time? Give yourself a minute to try and answer this. Now, for the answer... it is a yes. Why? Because all we have to really do is compute our maximum profit at any given day i. And how do we go about keeping track of our maximum profit? Well, it is actually very similar to the question we have done before on maximum subarrays here, but instead of tracking the max sum, we are tracking the max profit. Using a simple 1D array will work here where each index i of the array represents the best profit you can make at day i.
Implementation in Python
First, we'll start with our initial tabulation of 0 profit.
def solution(prices: List[int]) -> int:
# initialization
max_profit = [0 for i in range(len(prices))]
As for the base case, since we need at least 2 days to make a profit (i.e., buy on a given day and sell thereafter) for all input arrays of length 1, we make a maximum profit of 0 (we don't want to buy any stock since there's no day 2 to sell; buying a stock will just make negative profit), but since max_profit[0] is already 0 from our initialization, then there's nothing to change here.
Now, we can start to work our way up from input arrays of length 2 with the following structure, where we want to calculate max_profit[i] using our previously computed solution of max_profit[i-1]. So how can we do this?
for i in range(1, len(prices)):
max_profit[i] = ...
I hope it's clear at this point that we can set max_profit[i] = max_profit[i-1] if max_profit[i-1] is greater than prices[i] - min(prices[:i]), otherwise we want to set max_profit[i] = prices[i] - min(prices[:i]).
Python slicing works such that prices[:i] is a subarray of prices from index 0 to index i-1
But calling min(prices[:i]) can waste unnecessary computation time and really all we want is the lowest price up to index i-1, and we can do this by simply creating a new variable called min_price and keep track of it throughout the while loop instead of calling min().
Finally, we can just return max_profit[len(prices) - 1] as our final solution so that our completed solution will look like:
def solution(prices: List[int]) -> int:
if len(prices) == 0:
return 0
# initialization
max_profit = [0 for i in range(len(prices))]
min_price = prices[0]
for i in range(1, len(prices)):
if prices[i] < min_price:
min_price = prices[i]
max_profit[i] = max(prices[i] - min_price, max_profit[i - 1])
return max_profit[len(prices) - 1]
Hopefully that all makes sense and see you in the next chapter of the series. Thanks for reading!