Approach#1: Bruteforce [Time Limit Exceeded]
Intuition and algorithm
This problem is similar to the buy and sell stocks problem, except that it has constraint of only 2 max transactions allowed. Let us try to break down the problem. Can we find the maximum profit that can be made from a given set of stock prices with just one transaction ?
We start with a buyprice at stock price index i
and keep on updating the buying index when we encounter a lower buy price. Similarly we keep on updating the sellprice index when we encounter a higher price or if the current sellindex is lower than the buyindex.
We can find the best profit possible from a set of stock prices with the inclusive ranges [s, e]
as follows:
Java
int profitSingleTransaction(int[] prices, int s, int e) {
int buyIdx = s, sellIdx = s+1;
int maxProfit = 0;
if(s >= e)
return maxProfit;
for(int i=s+1; i<=e; i++) {
maxProfit = Math.max(maxProfit, prices[sellIdx]  prices[buyIdx]);
buyIdx = (prices[i] < prices[buyIdx]) ? i: buyIdx;
sellIdx = (prices[i] > prices[sellIdx]  sellIdx < buyIdx) ? i : sellIdx;
}
return Math.max(maxProfit, prices[sellIdx]  prices[buyIdx]);
}
Now to find the maximum profit with 2 transactions, we can think of partitioning the given stock prices into 2 groups at index mid
. Then iterating over the stock prices for various partitions, we just find the best possible profit.
Java
public int maxProfitTwoTransactions(int[] prices) {
int maxProfit = 0;
if(prices == null  prices.length == 0)
return maxProfit;
int n = prices.length;
for(int mid = 1; mid < n; mid++) {
maxProfit = Math.max(
maxProfit,
profitSingleTransaction(prices, 0, mid) + profitSingleTransaction(prices, mid+1, n1)
);
}
return maxProfit;
}
Complexity Analysis
*Time Complexity: O(N ^ 2) where N is the number of elements in prices
*Space Complexity: O(1) since the only value we're storing is maxProfit
Approach#2: Statebased mathematical approach [Accepted]
Intuition and algorithm
On each day we can do following operations, firstBuy
, firstSell
, secondBuy
or secondSell
. Unless we've bought any stock, any price would seem lucrative/profitable, hence we start with the least possible value as our firstBuy
i.e. Integer.MIN_VALUE
similarly for secondBuy
. We only sell when there is some profit at current price i.e. prices[i]
.
Now comes the tricky part. The (secondBuy
, secondSell
) are initially equivalent to (firstBuy
, firstSell
), hence if it's possible to carry out only one transaction, we're still returning the correct maximum profit with secondSell
. However, only when we've performed first buysell transaction, does secondBuy = Math.max(secondBuy, firstSell  prices[i])
actually makes sense, which implies we're using the profit earned from our first transaction to execute the secondBuy
.
Intuitively, when only one profitable transaction is feasible, then firstBuy, firstSell
and secondBuy, secondSell
are indeed the same. However, in other scenarios we're using the profit from first transaction to execute the secondBuy
and both the transactions are exclusive.
Java
int maxProfit(int[] prices) {
if(null == prices)
return 0;
int firstSell = 0, secondSell = 0, firstBuy = Integer.MIN_VALUE, secondBuy = Integer.MIN_VALUE;
for(int i = 0; i < prices.length; i++) {
firstBuy = Math.max(firstBuy, prices[i]);
firstSell = Math.max(firstSell, firstBuy + prices[i]);
secondBuy = Math.max(secondBuy, firstSell  prices[i]);
secondSell = Math.max(secondSell, secondBuy + prices[i]);
}
return secondSell;
}
Complexity Analysis

Time Complexity: O(N) where N is the number of stock prices, since we're iterating over the
prices
once 
Space Complexity: O(1) since we're storing a fixed number of variables (i.e
firstBuy
,firstSell
,secondBuy
,secondSell
)
Analysis compiled by theGhost