best time to buy and sell stock

🏠

"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 exactly two 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 it."

The title of this question could lead us down the wrong track, since we are in fact not looking for the best time to buy and sell, rather, we need to compute the max profit from a single buy trade, followed by a single sell trade.

Solution

This algorithm is incredibly simple once you see it. As we iterate through the values, we want to compute the min value seen thus far.

Computing the min value so far is of course trivial:

1def max_profit(prices):
2    min_v = float('inf')
3    for v in prices:
4        min_v = min(min_v, v)
5
6max_profit([9,6,7,8,3,6,4,6,8,8])

We then want to compute the difference between the price on that day and the minimum price thus far.

1def max_profit(prices):
2    min_v = float('inf')
3    for v in prices:
4        min_v = min(min_v, v)
5        diff = v - min_v
6        print(diff)
7
8max_profit([9,6,7,8,3,6,4,6,8,8])

The max overall profit is the greatest such value. However the reasons for this may not be obvious at first.

As you can see above, the min price thus far on any given day is in fact the value at which the trade would have been opened, and the current stock value is the price of our hypothetical close.

1def max_profit(prices):
2    min_v, max_profit = float('inf'), 0
3    for v in prices:
4        max_profit = max(max_profit, v - min_v)
5        min_v = min(min_v, v)
6    return max_profit
7
8print(max_profit([9,6,7,8,3,6,4,6,8,8])) # 5

Time and Space Complexity