# Solution by theGhost

• #### Approach#1: Brute-force [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 buy-price 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 sell-price index when we encounter a higher price or if the current sell-index is lower than the buy-index.

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]);

sellIdx = (prices[i] > prices[sellIdx] || sellIdx < buyIdx) ? i : sellIdx;

}

}

``````

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, n-1)
);
}

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: State-based 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 buy-sell 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++) {

firstSell = Math.max(firstSell, firstBuy + 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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.