123_Best Time to Buy and Sell Stock III

Say you have an array for which the i_th element 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:

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.

Solution:

Idea:

• Divide and Conquer: suppose the first transaction occurs in A[0, i] and the second transaction happens in A[i, n], then the sum of two profits is the total profit for that i.

• Do a forward loop to compute the highest profit we can get when we sell on each day.

• Do a backward loop to compute the highest profit we can get when we buy the second share on each day.

Time Complexity: $O(n)$

Space Complexity: $O(n)$

def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    if len(prices) < 2 :
        return 0

    # forward step
    # for each day, we record maximum profit if we sell on that day
    profit_left = [0]*len(prices)
    min_price = prices[0]        
    for i in range(1, len(prices)) :
        profit_left[i] = max(profit_left[i-1], prices[i] - min_price)
        min_price = min(min_price, prices[i])

    # backward step
    # for each day, find the maximum profit if we make the second buy
    # on that day
    max_price = prices[-1] 
    max_profit = max(profit_left[-1], profit_left[-2])
    for j in range(len(prices)-2, 0, -1) :
        max_profit = max(max_profit, max_price-prices[j]+profit_left[j-1])
        max_price = max(max_price, prices[j])
    max_profit = max(max_profit, max_price-prices[0])

    return max_profit