⚡Flashcard Drill➔
NeetCode #720LC-309Medium2-D Dynamic ProgrammingNC 150NC 250
← Back to All Problems

#720 · #309 · Best Time to Buy and Sell Stock with Cooldown(最佳买卖股票时机含冷冻期)

📌 Problem Statement & Constraints

Given prices, find the maximum profit from any number of buy/sell transactions, with the restriction that after selling you must wait one day before buying again. You may hold at most one share at a time. Constraints: 1 <= prices.length <= 5000, 0 <= prices[i] <= 1000.

💡 Core Algorithmic Approaches

  1. Track three states per day: hold (owning a share), sold (sold today), and rest (not holding and free to buy).
  2. The transitions are hold = max(hold, rest - price), sold = hold_prev + price, and rest = max(rest, sold_prev).
  3. The cooldown is encoded by allowing a buy only from rest, which cannot be the state produced by a same-day sale.
  4. The answer is max(sold, rest) on the last day.

💻 Benchmark Python3 Implementation

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        hold = float("-inf")           # best profit while holding a share
        sold = 0                       # best profit ending today with a sale
        rest = 0                       # not holding, free to buy
        for p in prices:
            prev_hold, prev_sold = hold, sold
            hold = max(prev_hold, rest - p)   # keep holding, or buy from rest
            sold = prev_hold + p              # sell today
            rest = max(rest, prev_sold)       # cooldown / stay out
        return max(sold, rest)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass with constant work per day.
💾 Space Complexity
O(1): three scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Allowing a buy right after a sell: the buy must come from rest, which excludes the sold state of the same day.
  • Updating states in place without saving the previous values: sold depends on yesterday's hold, so capture the old values first.
  • Returning only sold: the best outcome may sit in rest when the last action was not a sale.
  • Seeding hold with 0: holding without having bought is invalid, so hold starts at negative infinity.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems