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
- Track three states per day:
hold(owning a share),sold(sold today), andrest(not holding and free to buy). - The transitions are
hold = max(hold, rest - price),sold = hold_prev + price, andrest = max(rest, sold_prev). - The cooldown is encoded by allowing a buy only from
rest, which cannot be the state produced by a same-day sale. - 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 thesoldstate of the same day. - Updating states in place without saving the previous values:
solddepends on yesterday'shold, so capture the old values first. - Returning only
sold: the best outcome may sit inrestwhen the last action was not a sale. - Seeding
holdwith 0: holding without having bought is invalid, soholdstarts 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.