Problem 544786 · medium · Phase 05 Advanced Algorithms & Graphs

Trades With a Cooling-Off Day

dynamic programming · 1-D dp · state machine · stock trading

A trading club follows one share's price, prices[i] on day i. A member may hold at most one share at a time and may buy or sell at most once per day. Club rules add a cooling-off day: after selling, the member may not buy on the very next day. There is no fee and no limit on the number of round trips. Return the maximum total profit (0 if no trade helps).

Examples

Input:  prices = [3, 1, 4, 8, 2, 9]
Output: 10
Explanation: buy at 1, sell at 4, cool off on day 3, buy at 2, sell at 9.
Without the rule, 1 -> 8 and 2 -> 9 would give 14, but buying on day 4 right after selling on day 3 is forbidden.

Input:  prices = [5, 4, 3]
Output: 0

Constraints

  • 0 <= len(prices) <= 10**5
  • 0 <= prices[i] <= 10**5
  • Target complexity: O(n) time.

Goals

  • Model a day-after-sale restriction with a third state
  • Update all states simultaneously from the previous day
Starting Python…