Hard

Best Time to Buy and Sell Stock III

LAB

Return the maximum profit from at most two buy-sell transactions, holding at most one share at a time.

EXAMPLES

Example 1

Input
{
  "prices": [
    3,
    3,
    5,
    0,
    0,
    3,
    1,
    4
  ]
}

Output
6

FUNCTION SHAPE

prices: intArray→int

SOLUTION NOTE

Special case of k transactions where k=2. Track remaining transactions and holding state.

Reveal reference solution +

pythonREFERENCE

def maxProfit(self, prices: List[int]) -> int:
    @cache
    def dp(i, k, holding):
        if i == len(prices) or k == 0:
            return 0
        if holding:
            return max(dp(i + 1, k, True), dp(i + 1, k - 1, False) + prices[i])
        else:
            return max(dp(i + 1, k, False), dp(i + 1, k, True) - prices[i])

    return dp(0, 2, False)

TimeO(n)

SpaceO(n)

Open on LeetCode ↗