Stock Trading DP

📈 Stock Trading DP: Your Guide to Maximum Profit

The Magical Candy Shop Story

Imagine you have a magic candy shop. Every day, the candy prices change. Some days candy is cheap. Some days it’s expensive.

Your goal? Buy candy when it’s cheap. Sell when it’s expensive. Make the most coins!

But here’s the twist: There are special rules about when you can buy and sell. Let’s learn them together!

Part 1: Best Time to Buy and Sell Stock I

🎯 The Simple Rule

You can only buy once and sell once.

Think of it like this: You have one golden ticket to buy candy, and one golden ticket to sell it.

The Story of Little Maya

Maya visits the candy shop for 6 days. Here are the prices:

Day:    1    2    3    4    5    6
Price:  7    1    5    3    6    4
        ↓    ↓    ↓    ↓    ↓    ↓
       Bad  BEST  Ok  Bad  BEST  Ok
            BUY            SELL

What should Maya do?

• Buy on Day 2 (price = 1) 🛒
• Sell on Day 5 (price = 6) 💰
• Profit = 6 - 1 = 5 coins!

The Magic Formula

As we walk through each day, we ask two questions:

1. Is today’s price the lowest I’ve seen? → Update minimum
2. If I sell today, what’s my profit? → Update maximum profit

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;

    for (int price : prices) {
        // Is this the cheapest day?
        if (price < minPrice) {
            minPrice = price;
        }
        // What if I sell today?
        int profit = price - minPrice;
        if (profit > maxProfit) {
            maxProfit = profit;
        }
    }
    return maxProfit;
}

Why This Works

graph TD
    A["Start: Day 1"] --> B{Is price lowest?}
    B -->|Yes| C["Remember this price"]
    B -->|No| D{Calculate profit}
    C --> D
    D --> E{Is profit best?}
    E -->|Yes| F["Remember this profit"]
    E -->|No| G["Move to next day"]
    F --> G
    G --> H{More days?}
    H -->|Yes| B
    H -->|No| I["Return best profit"]

Real Example Walkthrough

Answer: 5 coins!

Edge Cases

What if prices only go down?

Prices: [5, 4, 3, 2, 1]

No matter when you buy, you’ll lose money. So the answer is 0 (don’t trade at all!).

What if prices stay the same?

Prices: [3, 3, 3, 3]

No profit possible. Answer is 0.

Part 2: Best Time to Buy and Sell with Cooldown

🎯 The New Rules

Now the candy shop has a special rule:

After you sell, you must rest for one day before buying again.

Think of it like this: After selling candy, you’re so tired you need to nap the next day!

The Story of Jake and His Energy

Jake can be in three states:

1. HOLD 🎒 - Jake has candy in his bag
2. SOLD 💤 - Jake just sold. He’s tired. He’s cooling down.
3. REST ⚡ - Jake has no candy and is ready to buy

graph TD
    REST["REST ⚡<br>Ready to buy"] -->|Buy| HOLD["HOLD 🎒<br>Has candy"]
    REST -->|Do nothing| REST
    HOLD -->|Sell| SOLD["SOLD 💤<br>Cooling down"]
    HOLD -->|Do nothing| HOLD
    SOLD -->|Must rest| REST

The Magic Formula

For each state, we track the maximum profit we can have:

public int maxProfit(int[] prices) {
    if (prices.length <= 1) return 0;

    // On day 0:
    int hold = -prices[0];  // Bought today
    int sold = 0;           // Can't sell (no stock)
    int rest = 0;           // Doing nothing

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

        // HOLD: either keep holding OR buy today
        hold = Math.max(prevHold, prevRest - prices[i]);

        // SOLD: must have been holding, sell today
        sold = prevHold + prices[i];

        // REST: either was resting OR finished cooldown
        rest = Math.max(prevRest, prevSold);
    }

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

Understanding Each Line

hold = Math.max(prevHold, prevRest - prices[i])

• Either: Keep the candy from yesterday (prevHold)
• Or: Was resting, now buying today (prevRest - prices[i])

sold = prevHold + prices[i]

• Must have been holding candy
• Sell it today for today’s price

rest = Math.max(prevRest, prevSold)

• Either: Keep resting
• Or: Finished cooling down from selling

Real Example Walkthrough

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

Answer: max(3, 2) = 3 coins!

What happened?

1. Buy at price 1
2. Sell at price 3 → Profit = 2
3. Cooldown (can’t buy)
4. Buy at price 0
5. Sell at price 2 → Profit = 2

Total: 2 + 2 = 4… wait, that’s more than 3?

Let me recalculate more carefully:

Final Answer: max(sold=3, rest=2) = 3

The Key Insight

The cooldown forces us to think one step ahead. We can’t be greedy!

graph LR
    A["See low price"] --> B{Was I cooling down?}
    B -->|Yes| C[Can't buy today 😢]
    B -->|No| D["Buy! 🛒"]
    C --> E["Wait for tomorrow"]

Comparing Both Problems

Tips to Remember

Stock I - The Simple One

“Track the lowest price and the best profit”

Stock with Cooldown - The State Machine

“After selling, you must REST before BUYING again”

Common Mistakes

❌ Mistake 1: Forgetting you can choose NOT to trade

• If prices only go down, return 0!

❌ Mistake 2: Buying after selling without cooldown

• In cooldown problem, selling on Day 3 means you can’t buy on Day 4

❌ Mistake 3: Mixing up states

• HOLD = you have stock
• SOLD = you just sold, cooling down
• REST = ready to buy

You Did It! 🎉

Now you understand:

1. Stock I: One trade. Find lowest buy, highest sell after it.
2. Stock with Cooldown: Multiple trades. Three states. Rest after selling.

Remember Maya and Jake’s stories, and you’ll never forget these patterns!

Quick Code Reference

Stock I

int min = MAX, profit = 0;
for (int p : prices) {
    min = Math.min(min, p);
    profit = Math.max(profit, p - min);
}
return profit;

Stock with Cooldown

int hold = -prices[0], sold = 0, rest = 0;
for (int i = 1; i < n; i++) {
    int h = hold, s = sold;
    hold = Math.max(h, rest - prices[i]);
    sold = h + prices[i];
    rest = Math.max(rest, s);
}
return Math.max(sold, rest);

You’re ready to trade like a pro! 🚀