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.

// Brute-force: Amasochist's approach
int maxProfit(int[] prices) {
    return dfs(0, false);
}
int dfs(int day, boolean holding) {
    if (day >= prices.length) return 0;
    if (holding) {
        int sell = prices[day] + dfs(day + 2, false); // Sell and take a nap
        int keep = dfs(day + 1, true); // Keep holding and muttering
        return Math.max(sell, keep);
    } else {
        int buy = -prices[day] + dfs(day + 1, true);
        int skip = dfs(day + 1, false);
        return Math.max(buy, skip);
    }
}
// DP solution, coming up—no exponential tears needed!

🧠 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)
• On day 0:

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

  (Just bought, so you’re in the hole. That’s trading.)
• 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
  

• At the end: max of sold/rest (you can’t finish holding, unless you like losing money).