The O(n) Club: Best Time to Buy and Sell Stock IV: The Art of Squeezing Profit From k Attempts

The O(n) Club: Best Time to Buy and Sell Stock IV — The Art of Squeezing Profit From k Attempts

⚡ TL;DR

You want max profit from stock prices, but only k opportunities to look clever before the market says, ‘Sorry, come back next quarter.’ Brute-force recursion? Only if you want your laptop to invent cold fusion. Java shortcut below:

// Unlimited trades? Forget DP.
if (k >= prices.length / 2) {
  int profit = 0;
  for (int i = 1; i < prices.length; i++)
    profit += Math.max(0, prices[i] - prices[i - 1]);
  return profit;
}

🧠 How Devs Usually Mess This Up

Step 1: Write a cute brute-force recursion that checks every buy/sell combo. Step 2: Wait longer than daylight savings for a result. Step 3: Realize you’ve confused the word “transaction” and just bought and sold your sanity.

Also: many skip the unlimited transaction shortcut. That’s like running a marathon in hiking boots while someone shouts, “Just take a bike, dude.”

🔍 What’s Actually Going On

Think of every transaction as an all-you-can-eat coupon, but you only get k. You want to spend them when the food (stock price) is at peak value, not when the kitchen’s out of fries. That means keeping track of two things for every day and every precious coupon:

• Holding stock (because you bought, hoping for a rally)
• Not holding (sold already, counting your virtual cash)

Our DP approach shuffles you through these scenarios so you don’t end up selling low and buying high, or vice versa—like that one friend who invests in Beanie Babies.

🛠️ PseudoCode

• If k >= n/2, pretend you’re a Wall Street wolf and pocket all the upswings:
  for each day i: profit += max(0, price[i] - price[i-1])
• Otherwise, set up two DP arrays of size k+1:
  buy[t] = max profit after t-th buy (currently holding)
sell[t] = max profit after t-th sell (not holding)
• Initialize:
  buy[0...k] = Integer.MIN_VALUE; sell[0...k] = 0
• For each price, for t = 1..k:
  buy[t] = max(buy[t], sell[t-1] - price)
sell[t] = max(sell[t], buy[t] + price)
  Decide: waste your coupon today, or wait for a juicier deal?
• Your answer: sell[k]. Only the cool, not-holding crowd gets paid.

💻 The Code

public int maxProfit(int k, int[] prices) {
    if (prices == null || prices.length == 0) return 0;
    int n = prices.length;
    // Unlimited trades? Sum all good days.
    if (k >= n / 2) {
        int profit = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        }
        return profit;
    }
    int[] buy = new int[k + 1];
    int[] sell = new int[k + 1];
    Arrays.fill(buy, Integer.MIN_VALUE);
    for (int price : prices) {
        for (int t = 1; t <= k; t++) {
            buy[t] = Math.max(buy[t], sell[t - 1] - price);
            sell[t] = Math.max(sell[t], buy[t] + price);
        }
    }
    return sell[k];
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Empty prices? k = 0? You’re out—don’t search for bugs.
• If k >= n/2: Skip the DP. No one likes unnecessary work, not even CPUs.
• Don’t forget: Arrays.fill(buy, Integer.MIN_VALUE). Otherwise, you’ll believe you can buy at price zero on Mars.
• Time & Space: O(nk) for all you DP lovers, O(n) when k is a wild child.

🧠 Interviewer Brain-Tattoo

“DP isn’t just a resume word—it’s the difference between instant rejection and instant promotion. Remember: trade like a machine, with memory.”