Member-only story
Dynamic Programming Interview Questions: How to Maximize Stock Profits
Find the maximum profit given a list of stock prices
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.
Honestly, I just choose questions randomly that I thought would be fun and they seem to all be coincidentally better for a bottom-up approach. 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…
