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.

Solution

Use two dynamic programming array. One to keep the best profit from left, one to keep the best profit from right.

The best profit of two transactions is the max of vertical sum of left array and right array.

Because on any single day, the sum of left and right best profit on that day represents the profit from two transactions.

Python

def maxProfit(self, prices):
        if prices == []:
            return 0

        n = len(prices)
        lprofits = [0] * n
        rprofits = [0] * n
        lowest = prices[0]
        for i in range(1, n):
            lowest = min(lowest, prices[i])
            lprofits[i] = max(prices[i] - lowest, lprofits[i-1])

        highest = prices[-1]
        for i in range(n - 2, -1, -1):
            highest = max(highest, prices[i])
            rprofits[i] = max(highest - prices[i], rprofits[i+1])

        maxProfit = max( [lprofits[i] + rprofits[i] for i in range(n)])

        return maxProfit

Complexity Analysis:

Time: O(n)

Space: O(n)