📈 Stock Trading DP: Become a Time-Traveling Trader!
Imagine you have a magical crystal ball that shows you stock prices for the next few days. You can see exactly how much a stock will cost on Monday, Tuesday, Wednesday, and so on.
Now here’s the fun part: When should you buy? When should you sell? And sometimes, you might need to take a break before trading again!
This is the adventure of Stock Trading Dynamic Programming — where we become the smartest traders in the universe!
🎯 Our Trading Adventures
We’ll master two exciting challenges:
- Best Time to Buy and Sell Stock I — One simple trade to make the most money
- Best Time to Buy and Sell with Cooldown — Multiple trades, but with a rest period
Let’s begin our journey!
🥇 Part 1: Best Time to Buy and Sell Stock I
The Story
Meet little Timmy. He has a lemonade stand, but he wants to try something new — buying and selling toy stocks!
His dad shows him the toy stock prices for the week:
| Day | Monday | Tuesday | Wednesday | Thursday | Friday |
|---|---|---|---|---|---|
| Price | $7 | $1 | $5 | $3 | $6 |
Timmy can buy once and sell once. He wants to make the biggest profit possible!
Timmy’s Thinking
- Buy on Monday ($7), sell on Friday ($6)? Loss of $1 😢
- Buy on Tuesday ($1), sell on Wednesday ($5)? Profit of $4 😊
- Buy on Tuesday ($1), sell on Friday ($6)? Profit of $5 🎉
The best answer: Buy at $1, Sell at $6 = $5 profit!
🧠 The Simple Rule
Buy LOW, Sell HIGH — but sell AFTER you buy!
We need to find:
- The smallest price to buy
- The biggest price after that day to sell
🔍 How the Magic Works
Think of it like this:
- Walk through each day
- Keep track of the lowest price so far
- At each day, check: “If I sell today, how much do I make?”
- Remember the best profit you’ve seen
graph TD A["Start with Day 1"] --> B["Track Minimum Price"] B --> C["Calculate Profit if Sold Today"] C --> D{Is this the best profit?} D -->|Yes| E["Update Best Profit"] D -->|No| F["Keep Current Best"] E --> G["Move to Next Day"] F --> G G --> H{More Days?} H -->|Yes| B H -->|No| I["Return Best Profit"]
💻 The Code
def maxProfit(prices):
if not prices:
return 0
min_price = prices[0]
max_profit = 0
for price in prices:
# Update minimum if found lower
min_price = min(min_price, price)
# Check profit if we sell today
profit = price - min_price
# Update best profit
max_profit = max(max_profit, profit)
return max_profit
Let’s Trace Through!
Prices: [7, 1, 5, 3, 6]
| Day | Price | Min So Far | Profit Today | Best Profit |
|---|---|---|---|---|
| 1 | 7 | 7 | 0 | 0 |
| 2 | 1 | 1 | 0 | 0 |
| 3 | 5 | 1 | 4 | 4 |
| 4 | 3 | 1 | 2 | 4 |
| 5 | 6 | 1 | 5 | 5 ✓ |
Answer: $5 profit! 🎉
🎨 Visual Understanding
Imagine the prices as a mountain range:
7
▲
│
│ 6
│ ▲
│ 5 │
│ ▲ │
│ │ 3 │
│ │ ▲ │
│ 1 │ │ │
│ ▲ │ │ │
────┴──┴──┴──┴──┴───
Mon Tue Wed Thu Fri
We want to buy at the valley ($1) and sell at the highest peak after it ($6)!
⚡ Why This Works
- Time Complexity: O(n) — we look at each price once
- Space Complexity: O(1) — we only remember 2 numbers
It’s super fast because we’re clever — we don’t compare every pair of days. We just remember the best buy price and check each sell price!
🧊 Part 2: Best Time to Buy and Sell with Cooldown
The New Challenge
Now Timmy is a bit older and wants to be a pro trader! But there’s a new rule:
After you sell, you must WAIT one day before buying again!
It’s like the stock market is saying: “Take a break! Cool down! Rest your brain!”
The Rules
- You can do many trades (buy-sell, buy-sell, …)
- After selling, you must skip one day before buying again
- You can’t hold multiple stocks (sell before you buy again)
🎭 The Three States
Imagine you’re a trader with three possible moods each day:
- HOLD 📦 — “I own a stock right now”
- SOLD 💰 — “I just sold today! Time to rest tomorrow”
- REST 😴 — “I’m cooling down or waiting to buy”
graph LR REST["REST 😴"] -->|Buy| HOLD["HOLD 📦"] HOLD -->|Sell| SOLD["SOLD 💰"] SOLD -->|Cooldown| REST HOLD -->|Keep| HOLD REST -->|Wait| REST
🎲 State Transitions Explained
Let’s think about what can happen each day:
From REST 😴
- Buy a stock → Go to HOLD
- Do nothing → Stay in REST
From HOLD 📦
- Sell the stock → Go to SOLD (and make money!)
- Keep holding → Stay in HOLD
From SOLD 💰
- Must cooldown → Go to REST (no choice!)
🧮 The DP Magic Formula
For each day, we calculate the best money we can have in each state:
hold[i] = max(hold[i-1], rest[i-1] - price[i])
"keep holding" OR "was resting, now buy"
sold[i] = hold[i-1] + price[i]
"was holding, now sell"
rest[i] = max(rest[i-1], sold[i-1])
"keep resting" OR "finished cooldown"
💻 The Code
def maxProfit(prices):
if len(prices) <= 1:
return 0
# Initialize states
hold = -prices[0] # Bought on day 0
sold = 0 # Can't sell on day 0
rest = 0 # Starting fresh
for price in prices[1:]:
prev_hold = hold
prev_sold = sold
prev_rest = rest
# Update each state
hold = max(prev_hold, prev_rest - price)
sold = prev_hold + price
rest = max(prev_rest, prev_sold)
# Best profit: either just sold or resting
return max(sold, rest)
📊 Example Walkthrough
Prices: [1, 2, 3, 0, 2]
| Day | Price | HOLD | SOLD | REST | Explanation |
|---|---|---|---|---|---|
| 0 | 1 | -1 | 0 | 0 | Buy: -1, Can’t sell, Fresh start |
| 1 | 2 | -1 | 1 | 0 | Keep or buy, Sell: -1+2=1, Rest |
| 2 | 3 | -1 | 2 | 1 | Keep, Sell: -1+3=2, Cooled down |
| 3 | 0 | 1 | -1 | 2 | Buy: 1-0=1, Sell: -1+0=-1, Rest |
| 4 | 2 | 1 | 3 | 2 | Keep, Sell: 1+2=3, Rest |
Answer: max(3, 2) = $3 profit! 🎉
What Happened?
- Buy at $1 (Day 0)
- Sell at $2 (Day 1) → Profit: $1
- Cooldown (Day 2) → Rest
- Buy at $0 (Day 3)
- Sell at $2 (Day 4) → Profit: $2
Total: $1 + $2 = $3!
🎢 The State Machine Journey
graph TD D0["Day 0: Buy at $1"] --> D1["Day 1: Sell at $2"] D1 --> D2["Day 2: COOLDOWN"] D2 --> D3["Day 3: Buy at $0"] D3 --> D4["Day 4: Sell at $2"] style D0 fill:#e8f5e9 style D1 fill:#fff3e0 style D2 fill:#e3f2fd style D3 fill:#e8f5e9 style D4 fill:#fff3e0
⚡ Complexity
- Time: O(n) — one pass through prices
- Space: O(1) — just 3 variables!
🎓 Key Takeaways
Stock Trading I
| Concept | Remember |
|---|---|
| Goal | One buy, one sell, max profit |
| Strategy | Track minimum, check each sell |
| Time | O(n) |
| Space | O(1) |
Stock Trading with Cooldown
| Concept | Remember |
|---|---|
| Goal | Multiple trades with rest day |
| Strategy | 3 states: HOLD, SOLD, REST |
| Transition | SOLD must go to REST |
| Time | O(n) |
| Space | O(1) |
🌟 The Big Picture
Dynamic Programming for stocks is like having a smart diary:
- Remember the past — What was the best position yesterday?
- Make smart choices today — Buy, sell, or wait?
- Build towards tomorrow — Each decision affects future options
You’re not just trading — you’re time traveling through possibilities and picking the best path!
🚀 You Did It!
Congratulations! You now understand:
- ✅ How to find the best single trade
- ✅ How to handle cooldown periods
- ✅ The magic of state-based DP
- ✅ Why these solutions are super efficient
Go forth and conquer those stock problems! You’re a DP Trading Master now! 🏆