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 (firstBuy < -curPrice) firstBuy = -curPrice; // the max profit after you buy first stock
            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