LeetCode: 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 (ie, you must sell the stock before you buy again).

---

We can divide the array into two parts. We can find the maximum profit in prices[0:i] with one transaction and then find the maximum profit in prices[i+1:end] with one transaction. Then we can find the maximum sum of profit in prices[0:i] and profit in prices[i+1:end].

C++ Code:

/*
 * func: maximum_profit
 * goal: find the maximum profits if at most two transactions are permitted
 * @param prices: daily price of the stock
 * return: maximum profit
 */
/*
 * find the maximum profit in [0:i] + [i+1:end]
 * complexity: time O(n), space O(n)
 */
int maximum_profit(vector<int> &prices){
    if(prices.size() == 0){
        return 0;
    }
    vector<int> max_profit_array;
    int hold_price = prices[0];
    int max_profit = 0;
    for(const int &price : prices){
        int curr_profit = price - hold_price;
        max_profit = max(max_profit, curr_profit);
        max_profit_array.emplace_back(max_profit);
        if(price < hold_price){
            hold_price = price;
        }
    }
    
    int final_profit = max_profit_array.back();
    hold_price = prices[prices.size()-1];
    max_profit = 0;
    for(int i=prices.size()-2; i >= 0; --i){
        int curr_profit = hold_price - prices[i];
        max_profit = max(max_profit, curr_profit);
        final_profit = max(final_profit, max_profit + max_profit_array[i]);
        hold_price = max(hold_price, prices[i]);
    }
    
    return final_profit;
}

Python Code:

# func: find the maximum profit if at most two transactions are permitted
# @param prices: daily price of the stock
# @return: the max profit
# complexity: time O(n), space O(n)
def maximum_profit(prices):
    if not prices:
        return 0
    hold_price = prices[0]
    max_profit = 0
    max_profit_until = []
    for price in prices:
        curr_profit = price - hold_price
        #Find the maximum profit until now for one transaction
        max_profit = max(max_profit, curr_profit)
        max_profit_until.append(max_profit)
        hold_price = min(price, hold_price)

    #Find the maximum profit from i to the end
    hold_price = price[-1]
    max_profit = 0
    final_profit = max_profit_until[-1]
    for i in xrange(len(prices)-2, -1, -1):
        curr_profit = hold_price - prices[i]
        max_profit = max(max_profit, curr_profit)
        final_profit = max(final_profit, max_profit + max_profit_until[i])
        hold_price = max(hold_price, prices[i])
    return final_profit