Best Time to Buy and Sell Stock III

Problem Id: 123 Difficulty: Hard Tag: Array Tag: Dynamic Programming


Intuition

Since there could be at most 2 transactions (not k transactions), we could split the prices into 2 parts, left and right.

It's simple to get the maximum transaction for any i with prices[0:i] or prices[i:n] in O(n) time. So we could easily get the maximum 2 transactions with an additional loop. And the overall time complexity is O(n).

Solution


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0

        n = len(prices)
        left_profit = [0] * (n + 1)
        right_profit = [0] * (n + 1)

        min_price = prices[0]
        for i, p in enumerate(prices):
            if p < min_price:
                min_price = p
            left_profit[i + 1] = max(left_profit[i], p - min_price)

        max_price = prices[-1]
        for i in range(n - 1, -1, -1):
            p = prices[i]
            if p > max_price:
                max_price = p
            right_profit[i] = max(right_profit[i + 1], max_price - p)

        max_profit = 0
        for i in range(n):
            max_profit = max(max_profit, left_profit[i] + right_profit[i])
        return max_profit