Daily bit(e) of C++ | Best time to buy and sell stock
Daily bit(e) of C++ #282, Common interview problem: Best time to buy and sell stock.
Today, we will look at a common C++ interview problem: Best time to buy and sell stock.
Given information about stock prices as std::vector<int> where each element represents the price at that time, determine the maximum possible profit achievable with two transactions.
You can only hold one stock at a time and only do one buy or sell operation at each time.
For example, for {8,1,6,7,0,5}, the maximum profit is 11, achieved by two transactions: {buy:1, sell:7}, {buy:0, sell:5}.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/ejn937hqa.
Solution
Let’s start with a simpler problem and limit ourselves to a single transaction. With one transaction, we want to find the optimal combination of the time to buy (tb) and the time to sell (ts), for which the profit (price[ts]-price[tb]) is maximized.
If we consider selling at a given time, the maximum profit is achieved by buying at the minimum price we have seen (price[current]-min_price). And we calculate the total maximum in one pass over the array.
We can see the two-transaction version as splitting our problem into two chunks, i.e. for each index i, calculating max_profit(0,i)+max_profit(i+1,size()-1).
When calculating the single-pass solution, we already kept track of the maximum profit until each element. If we could calculate the maximum profit for the remainder of the array, then the total profit would be the sum, and we could keep track of the global maximum in one pass.
We can precalculate the values by flipping the problem around and considering each element as the place to buy, and instead of the best buy price, track the best sale price.
However, we can do even better. Consider that we are essentially calculating: (price[ts1]-price[tb1])+(price[ts2]-price[tb2]). We can reorder this formula into price[ts2]-(price[tb2]-(price[ts1]-price[tb1])), i.e. the first sale gives us a discount to the price of the second purchase.
This reformulation allows us to calculate the result in one pass with O(1) memory.
Thank you for sharing these nice solutions. However, it doesn't seem to give the correct result for the vector {1,2,3,4,5}. Both solutions give 4, but this is maximum profit with one transaction, not two. In the first solution, the suffix vector keeps track of the max(suffix[i+1], max - prices[i]) for each element i. But this would give the maximum profit achievable to the right, but including the current price, i.e [i..prices.size()). But in the description you say it should keep track of the maximum profit achievable to the right, but excluding the current price i, i.e. (i..prices.size()). Shouldn't the elements in the suffix vector be shifted by 1 to the left? So in this case suffix should be equal to [3, 2, 1, 0, 0] and not [4, 3, 2, 1, 0]. Also, since in the problem description it is stated that we want to find the maximum achievable profit with two transactions. But then we should not take into consideration the first and the last element in prices, since these will give the profits for a single transaction. In this case, I think the maximum achievable profit with two transactions is 3 via {buy:1, sell:3} + {buy:4, sell:5}.