Stock Trading DP

📈 Stock Trading DP: Become a Time-Traveling Stock Trader!

The Magic of Stock Trading DP

Imagine you have a time machine and a list of stock prices for every day of the week. You can travel back and see exactly what the price will be each day. Your mission? Buy low, sell high — and make the most money possible!

But here’s the twist: There are rules about when you can buy and sell. Sometimes you can only do it once. Sometimes you need to take a “rest day” after selling. Let’s explore both adventures!

🎯 Part 1: Best Time to Buy and Sell Stock I

The Simple Story

You’re a kid at a candy store, but instead of candy, you’re buying and selling one magic toy.

• You can buy the toy once
• You can sell the toy once
• You must buy before you sell

Your goal: Find the perfect buy day and the perfect sell day to make the most coins!

The Everyday Analogy 🍎

Think of it like buying apples at a market:

Buy on Tuesday ($1), Sell on Friday ($6) = $5 profit!

How Do We Solve This?

We walk through each day, keeping track of two things:

1. Lowest price seen so far (our best buying opportunity)
2. Maximum profit possible (if we sold today)

graph TD
    A["Start: Day 1"] --> B["Track minimum price"]
    B --> C["For each day"]
    C --> D{Is today's price<br>lower than minimum?}
    D -->|Yes| E["Update minimum"]
    D -->|No| F["Calculate profit&lt;br&gt;if sold today"]
    E --> G["Move to next day"]
    F --> H{Is this profit<br>better than best?}
    H -->|Yes| I["Update best profit"]
    H -->|No| G
    I --> G
    G --> C

The Code Magic ✨

function maxProfit(prices) {
  let minPrice = Infinity;
  let maxProfit = 0;

  for (let price of prices) {
    // Found a cheaper buy day?
    if (price < minPrice) {
      minPrice = price;
    }
    // Could we make more profit?
    let profit = price - minPrice;
    if (profit > maxProfit) {
      maxProfit = profit;
    }
  }

  return maxProfit;
}

Step-by-Step Example

Prices: [7, 1, 5, 3, 6, 4]

Answer: $5 (Buy at $1, sell at $6)

What If Prices Only Go Down? 📉

Prices: [7, 6, 4, 3, 1]

Every day is cheaper than before. If you buy on any day, you’d lose money selling later!

Answer: $0 (Don’t trade at all!)

Key Insights 💡

🎯 Part 2: Best Time to Buy Sell with Cooldown

The New Challenge

Now you’re a professional trader with more freedom… but also more rules!

New Powers:

• You can buy and sell multiple times
• Stack up your profits!

The Catch:

• After you sell, you must rest for one day (cooldown)
• You can’t buy the very next day after selling

The Everyday Analogy 🛋️

Imagine you’re trading baseball cards:

• You can trade as many times as you want
• But after each sale, you need one rest day to “recover”
• It’s like catching your breath between sprints!

The Three States

Every day, you’re in one of three states:

graph LR
    A["HOLD 📦<br>Own a stock"] --> B["SOLD 💰<br>Just sold today"]
    B --> C["REST 😴<br>Cooldown day"]
    C --> A
    C --> C
    A --> A

The State Machine Logic

Each day, we track the maximum money in each state:

HOLD today = max of:

• Keep holding (yesterday’s HOLD)
• Buy today (yesterday’s REST - today’s price)

SOLD today =

• Sell today (yesterday’s HOLD + today’s price)

REST today = max of:

• Stay resting (yesterday’s REST)
• Cooldown complete (yesterday’s SOLD)

The Code Magic ✨

function maxProfit(prices) {
  if (prices.length === 0) return 0;

  let hold = -prices[0]; // Bought on day 1
  let sold = 0;          // Never sold yet
  let rest = 0;          // Haven't done anything

  for (let i = 1; i < prices.length; i++) {
    let prevHold = hold;
    let prevSold = sold;
    let prevRest = rest;

    // Today's states
    hold = Math.max(prevHold, prevRest - prices[i]);
    sold = prevHold + prices[i];
    rest = Math.max(prevRest, prevSold);
  }

  // End: either just sold or resting
  return Math.max(sold, rest);
}

Step-by-Step Example

Prices: [1, 2, 3, 0, 2]

Answer: $3 (Buy→Sell, Rest, Buy→Sell)

The Journey Visualized

graph TD
    D1["Day 1: $1<br>🛒 BUY"] --> D2["Day 2: $2<br>💰 SELL #40;+$1#41;"]
    D2 --> D3["Day 3: $3<br>😴 REST #40;cooldown#41;"]
    D3 --> D4["Day 4: $0<br>🛒 BUY"]
    D4 --> D5["Day 5: $2<br>💰 SELL #40;+$2#41;"]
    D5 --> TOTAL["Total: $3"]

Why Not Sell on Day 3?

If you sold on Day 3 ($3 - $1 = $2 profit):

• Day 4 is cooldown, can’t buy
• Day 5 you buy at $2… but no day to sell!
• Total: only $2

The cooldown forces strategic thinking!

Key Insights 💡

🎓 Comparing Both Problems

🏆 Victory Checklist

After this lesson, you can:

• ✅ Find the best single buy/sell opportunity
• ✅ Handle the case when no profit is possible
• ✅ Understand the cooldown constraint
• ✅ Use state machines for complex trading rules
• ✅ Track multiple states efficiently

🌟 The Golden Rules

1. Track what matters — minimum price, current states
2. One pass is enough — no need for nested loops
3. States tell the story — HOLD, SOLD, REST cover everything
4. Cooldown = Forced patience — rest before next trade
5. Compare endings — final answer is max of valid end states

You’re now a Dynamic Programming Stock Trader! Whether it’s one trade or many with cooldowns, you’ve got the tools to maximize your profits. Go conquer those stock problems! 🚀