Here's an O(1) space, O(n) time algorithm with Java code.
Logic:
Let $P_i$ denote the price of the stock on day $i$.
- Calculate maximum profit for $1^{st}$ transaction by $selling$ at or before day $i$ the usual way i.e. by calculating $Max(P_i - min[P_0...P_{i-1}])$. Call this $MaxProfit1_i$.
- If you had sold before day $i$ you can buy again at day $i$. If you do so, you'll need to deduct day $i$'s price from the 1st transaction's profit. Then, the maximum leftover profit at day $i$ is $Max(P_i - MaxProfit1_i)$. Call this $MaxLeftOver_i$.
- In the same vein, if you had bought the 2nd stock before day $i$, you can sell it at day $i$. If you do so, you add
day $i$'s price to the previous leftover profit to arrive at your profit at day $i$ with 2 transactions. Then, the maximum profit at day $i$ with 2 transactions is $Max(P_i + MaxLeftOver_i)$ - which is the final answer.
public int maxProfitWith2Transactions(int[] prices) {
if (prices.length == 0) return 0;
int minPrice = prices[0];
int maxProfitAfterFirstSell = 0;
int maxProfitLeftAfterSecondBuy = Integer.MIN_VALUE;
int maxProfitAfterSecondSell = 0;
for(int i = 1; i < prices.length; i++) {
final int p = prices[i];
maxProfitAfterFirstSell = Math.max(p - minPrice, maxProfitAfterFirstSell);
minPrice = Math.min(p, minPrice);
maxProfitLeftAfterSecondBuy = Math.max(maxProfitAfterFirstSell - p, maxProfitLeftAfterSecondBuy);
maxProfitAfterSecondSell = Math.max(p + maxProfitLeftAfterSecondBuy, maxProfitAfterSecondSell);
}
return maxProfitAfterSecondSell;
}
The below modified (slightly faster) variant of the above beats every solution in both space and time on LeetCode.
public int maxProfitWith2Transactions(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfitAfterFirstSell = 0;
int maxProfitLeftAfterSecondBuy = Integer.MIN_VALUE;
int maxProfitAfterSecondSell = 0;
for(int p : prices) {
minPrice = Math.min(p, minPrice);
maxProfitAfterFirstSell = Math.max(p - minPrice, maxProfitAfterFirstSell);
maxProfitLeftAfterSecondBuy = Math.max(maxProfitAfterFirstSell - p, maxProfitLeftAfterSecondBuy);
maxProfitAfterSecondSell = Math.max(p + maxProfitLeftAfterSecondBuy, maxProfitAfterSecondSell);
}
return maxProfitAfterSecondSell;
}
Here's the values that the above code calculates for prices 8, 10, 3, 7, 4, 9, 2, 3
.
Clearly, the max profit after 1 transaction is 6 (Buy at 3, sell at 9). After 2 transactions, the max profit is 9 (Buy at 3, Sell at 7, Buy again at 4, sell at 9).
$$\begin{array}{l|r r r r r r r r}
\text{$i$} & \text{0} & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} & \text{6} & \text{7} \\ \hline
\text{Price} & \text{8} & \text{10} & \text{3} & \text{7} & \text{4} & \text{9} & \text{2} & \text{3} \\ \\ \hline
\text{Lowest price seen} & \text{8} & \text{8} & \text{3} & \text{3} & \text{3} & \text{3} & \text{2} & \text{2} \\
\text{till day $i$} \\ \hline
\text{Max Profit if} & \text{x} & \text{2} & \text{2} & \text{4} & \text{4} & \text{6} & \text{6} & \text{6} \\
\text{bought at lowest} \\
\text{price before day $i$} \\
\text{and sold before} \\
\text{or on day $i$} \\ \hline
\text{Max Profit left if} & \text{x} & \text{-8} & \text{-1} & \text{-3} & \text{0} & \text{0} & \text{4} & \text{4} \\
\text{2nd buy is done on} \\
\text{day $i$.} \\
\text{= Max(PreviousRow$_i$ - $P_i$)} \\ \hline
\text{Max Profit if 2nd} & \text{x} & \text{2} & \text{2} & \text{4} & \text{6} & \text{9} & \text{9} & \text{9} \\
\text{stock is sold before} \\
\text{or on $P_i$} \\
\text{= Max(PreviousRow$_i$ + $P_i$)} \\ \hline
\end{array}$$