The O(n) Club: Stock Profit With Cooldown: Because Wall Street Needs Naps Too

The O(n) Club: Stock Profit With Cooldown—Because Wall Street Needs Naps Too

⚡ TL;DR

If you want to buy and sell stocks for max profit but there’s a weird HR rule: after every sale, you must take a chill day off (no trades for you). Brute force will fry your circuits. Enter: three-state dynamic programming. Java—because Python is too hipster for your boss.

🧠 How Devs Usually Mess This Up

Classic rookie moves incoming:

• Cooldown? What cooldown? They buy the very next day after selling, which the test case signature should just reject like a bad commit.
• Multiple bags—uh, stocks? They try to “hold” more than one stock at once. Sorry, Robinhood isn’t that easy.
• Mixing up buy and sell cooloffs. Cooldown is after a sell, not a buy. (You only get spa days for finishing, not starting.)

🔍 What’s Actually Going On

Imagine you’re the world’s laziest day trader, only able to do one thing each day—buy, sell, or just vibe in cooldown/rest. State transitions are your new best friends:

• Hold: You bought or you’re still holding. Fidgeting and hoping.
• Sold: You sold TODAY. Now, mandatory slippers and Netflix (that’s your cooldown).
• Rest: You finished cooldown (or did nothing)—free to buy again tomorrow.

Every action moves you between these moods. Model all three daily and greedily hoard max profit like cookie-clicker points.

🛠️ PseudoCode

• Track three variables per day:
  • hold: Profit if holding a stock right now
  • sold: Profit if you just sold
  • rest: Profit if you’re chilling (no stock held, not just sold)
• At the end: max of sold/rest (you can’t finish holding, unless you like losing money).

For each day, roll the states:

int prevSold = sold;
sold = hold + prices[i]; // Selling today
hold = Math.max(hold, rest - prices[i]); // Buy or hold
rest = Math.max(rest, prevSold); // Either resting or just cooled down

On day 0:

hold = -prices[0]; sold = 0; rest = 0;

(Just bought, so you’re in the hole. That’s trading.)