Medium

Best Time to Buy and Sell Stock with Cooldown

LAB

Return the maximum stock-trading profit when selling forces a one-day cooldown before buying again.

EXAMPLES

Example 1

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

Output
3

FUNCTION SHAPE

prices: intArray→int

SOLUTION NOTE

State machine DP with states: holding stock or not. After selling (i+2 because cooldown), after buying/holding (i+1).

Reveal reference solution +

pythonREFERENCE

def maxProfit(self, prices: List[int]) -> int:
    @cache
    def dp(i, holding):
        if i >= len(prices): return 0
        if holding:
            # Can sell or hold
            return max(prices[i] + dp(i+2, False), dp(i+1, True))
        else:
            # Can buy or skip
            return max(-prices[i] + dp(i+1, True), dp(i+1, False))

    return dp(0, False)

TimeO(n)

SpaceO(n)

Open on LeetCode ↗