loading

Stock with Cooldown — Step-by-Step Visualization

mediumLeetCode #309ArrayDynamic Programming

You are given an array `prices` where `prices[i]` is the price of a given stock on the `i-th` day. Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions: After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Algorithm Pattern

State Machine / Dynamic Programming

Key Idea

At any given day, we can be in one of three states: 1. **Buying**: We just bought a stock or were already holding. 2. **Selling**: We just sold a stock. 3. **Cooldown**: We are resting after a sale. By tracking the maximum profit for each state on each day, we can derive the overall maximum.

Step-by-Step Approach

  1. Define `buying[i]` as max profit at day `i` if we are holding a stock.
  2. Define `selling[i]` as max profit at day `i` if we just sold a stock.
  3. Transitions: - `buying[i] = max(buying[i-1], cooldown[i-1] - prices[i])` - `selling[i] = buying[i-1] + prices[i]` - `cooldown[i] = max(cooldown[i-1], selling[i-1])`.
  4. Initial values: `buying[0] = -prices[0]`, others 0.
  5. Result is `max(selling[n-1], cooldown[n-1])`.

Common Gotchas

  • The 'cooldown' state is mandatory only for the single day *immediately after* a sale.
  • Profit can be negative during the process (buying cost).

Related Problems

← All problems