## 123. Best Time to Buy and Sell Stock III

Say you have an array for which thei_thelement is the price of a given stock on day_i.

Design an algorithm to find the maximum profit. You may complete at most_two_transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

``````Input: [3,3,5,0,0,3,1,4]

Output: 6

Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
``````

Example 2:

``````Input: [1,2,3,4,5]

Output: 4

Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
``````

Example 3:

``````Input: [7,6,4,3,1]

Output: 0

Explanation: In this case, no transaction is done, i.e. max profit = 0.
``````

Thoughts:

1. DP
2. DP optimization: only tracking 4 variables:
3. Inspired from here

Code: DP:

``````class Solution {
public int maxProfit(int[] prices) {
// these four variables represent your profit after executing corresponding transaction
// in the beginning, your profit is 0.
// when you buy a stock ,the profit will be deducted of the price of stock.
int firstBuy = Integer.MIN_VALUE, firstSell = 0;
int secondBuy = Integer.MIN_VALUE, secondSell = 0;

for (int curPrice : prices) {
if (firstSell < firstBuy + curPrice) firstSell = firstBuy + curPrice; // the max profit after you sell it
if (secondBuy < firstSell - curPrice) secondBuy = firstSell - curPrice; // the max profit after you buy the second stock
if (secondSell < secondBuy + curPrice) secondSell = secondBuy + curPrice; // the max profit after you sell the second stock
}

return secondSell; // secondSell will be the max profit after passing the prices
}
}
``````

Code: DP Optimization

``````class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
hold1 = hold2 = -sys.maxint - 1 # INT.MIN_VAL
sell1 = sell2 = 0
# Assume we only have 0 money at first
for p in prices:
sell2 = max(sell2, hold2 + p) # The maximum if we've just sold 2nd stock so far.
hold2 = max(hold2, sell1 - p) # The maximum if we've just buy 2nd stock so far.
sell1 = max(sell1, hold1 + p) # The maximum if we've just sold 1nd stock so far.
hold1 = max(hold1, -p)        # The maximum if we've just buy  1st stock so far.

return sell2
``````