The O(n) Club: Maximum Product Subarray: Plot Twists, Negatives, and Contiguous Mayhem

The O(n) Club: Maximum Product Subarray — Plot Twists, Negatives, and Contiguous Mayhem

⚡ TL;DR

You’re hunting for the contiguous subarray whose product is the biggest drama queen (a.k.a., the maximum). Brute force works if you’re keen on heating your laptop, but a slick O(n) solution saves your sanity: keep tabs on both the running max and min, because negatives will punk you.

// Brute-force Java: Not recommended if you like your job
int maxProduct = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
    int prod = 1;
    for (int j = i; j < nums.length; j++) {
        prod *= nums[j];
        maxProduct = Math.max(maxProduct, prod);
    }
}

🧠 How Devs Usually Mess This Up

If you copy-paste your Maximum Subarray Sum logic and just swap ‘+’ for ‘*’, congrats on being haunted by negatives. That one rogue negative number flips everything, and you end up tracking the wrong contender. Ignoring zeros? Double whammy. Your product doesn’t survive across zeros—every time you hit one, it’s “new timeline, who dis?” territory.

🔍 What’s Actually Going On

Imagine you’re playing a weird game: every day’s result is multiplied into your score. Some days are wins (positives), some are epic fails (negatives), and zeros are hitting ‘restart.’ But two negatives in a row? You’re suddenly winning again—it’s like the stock market if the stock market were run by the Joker. Thus, you need to track both max and min products at each step, because sometimes your worst day flips and becomes your best.

🛠️ PseudoCode

• Initialize maxProd, minProd, result to the first array value.
• For every next element:
  • Store the current maxProd and minProd (because you’ll update both at once).
  • Update both with all three possibilities (the number itself, product with previous max, product with previous min):

    maxProd = max(curr, curr * prevMax, curr * prevMin);
    minProd = min(curr, curr * prevMax, curr * prevMin);

  • Update result = max(result, maxProd)
  • Zero detected? Both products get nuked. Begin again from zero like an optimistic goldfish.
• Return result as your answer. High five yourself for surviving the negatives.

💻 The Code

public int maxProduct(int[] nums) {
    int maxProd = nums[0];
    int minProd = nums[0];
    int result = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int curr = nums[i];
        int prevMax = maxProd;
        int prevMin = minProd;
        maxProd = Math.max(curr, Math.max(curr * prevMax, curr * prevMin));
        minProd = Math.min(curr, Math.min(curr * prevMax, curr * prevMin));
        result = Math.max(result, maxProd);
    }
    return result;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Negatives multiply trouble: Don’t rely on just the running max—negatives love switching sides.
• Zeroes are dealbreakers: Product subarrays can’t “jump” zeros. Start a new streak after every zero.
• Edge oddities: Single-element arrays? All negatives? All zeros? Your logic still needs to hold up, not just for happy-path inputs.
• Performance honesty: O(n) time, O(1) space. If your interview solution is O(n^2), the only thing it’s maximizing is recruiter eye-rolls.

🧠 Interviewer Brain-Tattoo

“Maximum Product Subarray turns yesterday’s disaster into tomorrow’s triumph with a single negative. Track both ends, or get whiplash.”