Problem Description

You are given an array prices where prices[i] represents the price of a stock on day i.

Your goal is to find the maximum profit you can achieve by buying and selling the stock multiple times, with the following rules:

1. Cooldown Rule: After you sell your stock, you cannot buy stock on the next day. This means there's a mandatory one-day cooldown period after each sale.

2. No Simultaneous Transactions: You cannot engage in multiple transactions at the same time. You must sell the stock you're holding before you can buy again.

3. Unlimited Transactions: You can complete as many buy-sell transactions as you want (subject to the above restrictions).

The problem asks you to determine the maximum profit possible given these constraints. You start with no stock and want to end with no stock, maximizing your profit through strategic buying and selling with the cooldown period in mind.

For example, if prices = [1, 2, 3, 0, 2], one optimal strategy would be:

• Buy on day 1 (price = 1)
• Sell on day 2 (price = 2), profit = 1
• Cooldown on day 3
• Buy on day 4 (price = 0)
• Sell on day 5 (price = 2), profit = 2
• Total profit = 3

The challenge is to find the optimal sequence of transactions that maximizes profit while respecting the cooldown period after each sale.

Intuition

The key insight is that at any given day, we can be in one of two states: either we're holding a stock or we're not holding a stock. This naturally leads us to think about the problem in terms of state transitions.

For each day i, we need to track the maximum profit we can achieve in each state:

• State 0: Not holding any stock
• State 1: Holding a stock

At each day, we face a decision based on our current state:

If we're not holding a stock (state 0):

• We can choose to do nothing and remain in state 0
• We can buy a stock (spending prices[i]), which transitions us to state 1

If we're holding a stock (state 1):

• We can choose to do nothing and remain in state 1
• We can sell the stock (gaining prices[i]), but here's the catch - due to the cooldown rule, we can't buy on the next day, so we jump to day i + 2 in state 0

This observation leads us to define a recursive function dfs(i, j) where:

• i represents the current day
• j represents our state (0 = not holding, 1 = holding)

The recurrence relation becomes:

• If j = 0 (not holding): dfs(i, 0) = max(dfs(i + 1, 0), -prices[i] + dfs(i + 1, 1))
  • Either skip this day or buy today
• If j = 1 (holding): dfs(i, 1) = max(dfs(i + 1, 1), prices[i] + dfs(i + 2, 0))
  • Either keep holding or sell today (with cooldown jumping to i + 2)

The base case is when i >= n (no more days), which returns 0 profit.

Since we start with no stock and want to maximize profit, we begin with dfs(0, 0). The memoization using @cache prevents us from recalculating the same states multiple times, making the solution efficient.

Solution Approach

The solution implements a top-down dynamic programming approach using memoization search. Here's how the implementation works:

Function Definition: The core function dfs(i, j) represents the maximum profit starting from day i with state j:

• i: Current day index
• j: Current state (0 = not holding stock, 1 = holding stock)

Base Case:

if i >= len(prices):
    return 0

When we've gone past the last day, there's no more profit to be made, so we return 0.

Recursive Cases:

1. Always available option - Do nothing:

   ans = dfs(i + 1, j)

   We can always choose to skip the current day and maintain our current state.

2. State-dependent decisions:

   If j = 1 (currently holding stock):

   ans = max(ans, prices[i] + dfs(i + 2, 0))

   • We can sell at prices[i]
   • Add the selling price to our profit
   • Due to cooldown, jump to day i + 2 with state 0 (not holding)

   If j = 0 (not holding stock):

   ans = max(ans, -prices[i] + dfs(i + 1, 1))

   • We can buy at prices[i]
   • Subtract the buying price from our profit
   • Move to day i + 1 with state 1 (holding stock)

Memoization: The @cache decorator automatically memoizes the function results. This prevents recalculation of the same (i, j) state combinations, reducing time complexity from exponential to O(n) where n is the number of days.

Starting Point:

return dfs(0, 0)

We start from day 0 with no stock in hand (state 0), which gives us the maximum profit achievable.

The beauty of this approach is that it naturally handles the cooldown constraint by jumping to i + 2 after selling, while the state tracking ensures we never hold multiple stocks simultaneously. The memoization transforms what would be an exponential time solution into a linear one with O(n) space complexity for the cache.

Example Walkthrough

Let's walk through the solution with prices = [1, 2, 4, 1].

We start with dfs(0, 0) - day 0, not holding stock.

Day 0, Not Holding (i=0, j=0):

• Option 1: Skip day 0 → dfs(1, 0)
• Option 2: Buy at price 1 → -1 + dfs(1, 1)

Let's explore Option 2 first: Buy at day 0

Day 1, Holding (i=1, j=1):

• Option 1: Keep holding → dfs(2, 1)
• Option 2: Sell at price 2 → 2 + dfs(3, 0) (cooldown jumps to day 3)

Taking Option 2: Sell at day 1

Day 3, Not Holding (i=3, j=0):

• Option 1: Skip day 3 → dfs(4, 0)
• Option 2: Buy at price 1 → -1 + dfs(4, 1)

Both lead to base case since i=4 >= len(prices)=4, returning 0. So dfs(3, 0) = max(0, -1 + 0) = 0

Backtracking: dfs(1, 1) = max(dfs(2, 1), 2 + 0) = 2

Now let's check the alternative at Day 1 - Keep holding:

Day 2, Holding (i=2, j=1):

• Option 1: Keep holding → dfs(3, 1)
• Option 2: Sell at price 4 → 4 + dfs(4, 0) (cooldown, but day 4 is out of bounds)

dfs(4, 0) returns 0 (base case) So dfs(2, 1) = max(dfs(3, 1), 4 + 0) = 4

Day 3, Holding (i=3, j=1):

• Option 1: Keep holding → dfs(4, 1) = 0 (base case)
• Option 2: Sell at price 1 → 1 + dfs(5, 0) = 1 + 0 = 1

So dfs(3, 1) = max(0, 1) = 1

Backtracking: dfs(2, 1) = max(1, 4) = 4 Therefore: dfs(1, 1) = max(4, 2) = 4

So buying on day 0 gives us: -1 + 4 = 3

Now checking Option 1 from the start: Skip day 0

Day 1, Not Holding (i=1, j=0):

• Option 1: Skip → dfs(2, 0)
• Option 2: Buy at price 2 → -2 + dfs(2, 1)

Following Option 2 (buy at day 1): dfs(2, 1) = 4 (calculated earlier) So this path gives: -2 + 4 = 2

Following Option 1 (skip to day 2): Day 2, Not Holding (i=2, j=0):

• Option 1: Skip → dfs(3, 0) = 0
• Option 2: Buy at price 4 → -4 + dfs(3, 1) = -4 + 1 = -3

So dfs(2, 0) = max(0, -3) = 0 Therefore dfs(1, 0) = max(0, 2) = 2

Final Result: dfs(0, 0) = max(dfs(1, 0), -1 + dfs(1, 1)) = max(2, 3) = 3

The optimal strategy: Buy on day 0 (price=1), sell on day 2 (price=4), giving profit = 3. The cooldown after selling on day 2 prevents buying on day 3, but that's fine since we achieve maximum profit.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array prices.

The function uses memoization with @cache decorator. The state space is defined by two parameters:

• i: index in prices array, ranging from 0 to n-1
• j: binary state (0 or 1), indicating whether currently holding stock

This creates at most 2n unique states (n positions × 2 holding states). Each state is computed exactly once due to memoization, and each computation involves O(1) operations. Therefore, the total time complexity is O(2n) = O(n).

The space complexity is O(n), where n is the length of the array prices.

The space is used for:

• The memoization cache storing up to 2n states: O(n)
• The recursion call stack with maximum depth n (in the worst case when always choosing to skip): O(n)

Since both contribute O(n) space, the overall space complexity is O(n).

Common Pitfalls

1. Incorrect Cooldown Implementation

A frequent mistake is forgetting to skip the cooldown day after selling, leading to incorrect state transitions.

Incorrect Implementation:

if holding_stock:
    # Wrong: Moving to next day instead of skipping cooldown
    max_profit = max(max_profit, prices[day] + dfs(day + 1, 0))

Correct Implementation:

if holding_stock:
    # Correct: Skip to day + 2 to enforce cooldown
    max_profit = max(max_profit, prices[day] + dfs(day + 2, 0))

2. State Representation Confusion

Mixing up what the states represent can lead to logic errors. Some developers use boolean values or different numbering schemes inconsistently.

Problematic Approach:

def dfs(day, can_buy):  # Using "can_buy" instead of "holding_stock"
    if can_buy:
        # This reverses the logic and becomes confusing
        max_profit = max(max_profit, -prices[day] + dfs(day + 1, False))
    else:
        max_profit = max(max_profit, prices[day] + dfs(day + 2, True))

Better Approach: Use clear, consistent state representation:

• 0 = not holding stock (can buy)
• 1 = holding stock (can sell)

3. Missing Import or Cache Decorator

Forgetting to import or apply the cache decorator results in exponential time complexity.

Without Memoization:

def dfs(day, holding_stock):  # Missing @cache decorator
    # This will have O(2^n) time complexity
    ...

With Proper Memoization:

from functools import cache

@cache
def dfs(day, holding_stock):
    # This ensures O(n) time complexity
    ...

4. Incorrect Profit Calculation

A subtle error is adding the buying price instead of subtracting it, or vice versa for selling.

Wrong:

if not holding_stock:
    # Wrong: Adding buying price instead of subtracting
    max_profit = max(max_profit, prices[day] + dfs(day + 1, 1))

Correct:

if not holding_stock:
    # Correct: Subtract buying price from profit
    max_profit = max(max_profit, -prices[day] + dfs(day + 1, 1))

5. Edge Case: Array Out of Bounds

When selling and jumping to day + 2, ensure the base case properly handles indices beyond the array length.

Potential Issue:

if day == len(prices):  # Too strict
    return 0
# Could miss valid states when day = len(prices) - 1 and selling

Robust Solution:

if day >= len(prices):  # Handles all out-of-bounds cases
    return 0

Prevention Tips:

1. Test with small examples: Trace through [1, 2, 3, 0, 2] manually to verify cooldown logic
2. Use descriptive variable names: holding_stock is clearer than j or state
3. Add comments: Document what each state represents and why cooldown requires day + 2
4. Verify profit signs: Remember that buying decreases profit (-price) and selling increases it (+price)