This will be a series of problems, getting more and more difficult.
Problem 1: Infinite buying/selling
Let’s say you have a list of stock prices, which reflect the price of the stock on a given day:
[7,1,5,3,6,8,4]
What’s the maximum profit you can get from buying/selling stocks, completing as many transactions as you like (i.e., buy one and sell one share of the stock multiple times)?
Answer: 9 (1 -> 5, 3 -> 8)
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Solution:
For me, the way I thought about this was that every long-term transaction can be broken into smaller transactions. Buying on day 4 and selling on day 6 is equivalent to buying on day 4 and selling on day 5, then buying on day 5 and selling on day 6. What determines whether you should buy on a given day? If the next day is greater!
So, now we get our very simple solution: We loop through every day, and we buy whenever the next day is greater than the current day.
def maxProfit(array): total = 0 for i in range(len(array) - 1): if array[i] < array[i + 1]: total += array[i-1] - array[i] return total
Problem 2: Buy/sell once
This is exactly the same problem, except you are only allowed to make one transaction the whole time.
Solution:
If you’re asked this in an interview, the safest thing to do is to think of a brute force solution.
O(n^2): Brute Force
The most basic solution is to try out every possible combination of buying and selling, and keep track of the best result.
E.g.: [7,1,5,3,6,8,4] → 5
[7,1,5,3,6,8,4] →3
…
There are n*(n-1)/2 total operations, or O(n) time.
O(n log n): Sorting
There is no way to sort here, because the order of the prices matters.
O(n): Single Pass
Based on the logic above, we’re not gonna see an interview problem with a brute force solution as the ideal solution (usually). So, you can deduce that this is the complexity of the ideal solution.
Because it’s a single pass, we can try selling at every location, and finding the maximum of that. The question is when would you buy it if you sell a stock today? You would buy it at the minimum up until that point. So, that’s all you have to do:
At every point, keep track of the minimum, and calculate current price - minimum. Take the maximum out of all of those.
def maxProfit(array): if len(array) < 2: return 0 minimum, best = array[0], 0 for i in array[1:]: if i < minimum: minimum = i elif i - minimum > best: best = i - minimum return total
Problem 3: Infinite buy/sell with cooldown
In this problem, you can buy/sell stocks as many times as you want. However, after you sell your stock, you cannot buy stock on next day.
On any given day, you have two options: you can either buy or sell stock. Both of them come with preconditions. First, in order to sell, the last transaction you’ve made was a sale. In order to buy, the last transaction you’ve made was a sale 2 days ago (or it’s your first time buying).
On every day, you have two numbers to keep track of. The highest amount you could’ve made if your last transaction was a sale, call it sell[i], and the highest amount you could’ve made if your last transaction was a buy, call it buy[i].
buy[i] = max(buy[i-1], sell[i-2] - prices[i])
Your last action was either already a buy, in which case you can’t buy again (buy[i-1]), or your last action was a sale two days ago, and you’re buying again today.
sell[i] = max(sell[i-1], buy[i-1] + prices[i])
Your last action was either already a sale (sell[i-1]), or your last action was buying, and you’re selling today.
That’s it! All we have to do now is pick a starting condition. buy[i] means your last transaction was a buy, so on the first day, buy[0] means we bought the stock, which means buy[0] = -1 * prices[0]. Likewise, sell[0] = 0, because we’re selling nothing.
Solution
def maxProfit(prices): buy = [0 for i in prices] sell = [0 for i in prices] buy[0] = -1 * prices[0] for i in range(1, len(prices)): if i < 2: buy[i] = max(buy[i-1], prices[i]) else: buy[i] = max(buy[i-1], sell[i-2] + prices[i]) sell[i] = max(sell[i-1], buy[i-1] + prices[i]) return sell[-1] #We're not gonna end on a purchase!
Cleaner Solution
Timewise, this is an amazing solution. It’s O(n) with one pass through the array. However, space-wise, it's inefficient. You don’t need to save your buy/sell information from 5 days ago! All you need is buy[i-1], sell[i-1], and sell[i-2]. Let’s rename these:
We can just refer to buy[i-1] as buy. After all, it’s just whatever information was previously stored in buy.
We can refer to sell[i-1] as sell.
We can refer to sell[i-2] as rest.
Now, let’s rewrite this code:
It’s important to note that doing something like a,b,c = 1,2,3 means that they happen simultaneously, so you don’t have to worry about the order you write the expressions in.
def maxProfit(prices): buy, sell, rest = -1 * prices[0],0,0 for price in prices[1:]: buy,sell,rest = max(buy, rest - price),\ max(sell, buy + price), sell return sell
Problem 4: Infinite buy/sell with a transaction fee
This is extremely similar to the previous problem. You have to keep track of two things: the maximum amount you can make if your last action was a buy, and the maximum amount you can make if your last action was a sale.
buy[i] = max(buy[i-1], sell[i-1] - prices[i])
This is exactly the same as before, except we don’t care about the cool-down period.
sell[i] = max(sell[i-1], buy[i-1] + prices[i] - fee)
Either you sold your stock earlier or you sell it today and pay a fee.
Right off the bat, we know we can simplify it. We only need to keep track of two variables: sell[i-1] and buy[i-1]. We know our initial conditions: buy = -1 * prices[0], and sell = 0
def maxProfit(prices, fee): buy, sell = -1 * prices[0], 0 for price in prices[1:]: buy, sell = max(buy, sell - price),\ max(sell, buy + price - fee) return sell # We don't want to end on a purchase