Maximum Product Subarray Explained | Java | Dynamic Programming | Blind 75

Have you ever tried to solve a maximum subarray problem where negative numbers completely flip your calculations?

When we see a problem like Maximum Product Subarray, our first instinct is usually:

“Isn’t this just Kadane’s Algorithm for Maximum Subarray Sum?”

When we write standard Kadane’s algorithm for sums:

currentMax = Math.max(nums[i], currentMax + nums[i]);

we rely on the fact that adding a number either increases or decreases our total predictably.

But with multiplication, negative numbers behave differently:

• Multiplying two negative numbers produces a positive result.
• A single negative number turns a huge positive product into a small negative product.
• The next negative number turns that small negative product back into a huge positive product!

Because of this, we must track both the maximum product and the minimum product at every position.

Companies like Amazon, Meta, Google, Microsoft, and Apple love this problem because it tests whether you can adapt classic dynamic programming patterns to handle edge cases like negative numbers and zeros.

In this article, we’ll build the intuition behind Maximum Product Subarray (LeetCode 152) from the Blind 75 list.

What You’ll Learn

By the end of this article, you’ll know:

• ✅ Why standard Kadane’s Algorithm fails for multiplication
• ✅ How negative numbers swap minimum and maximum products
• ✅ How zeros reset the contiguous product chain
• ✅ Approach 1: Brute Force (All Subarrays O(N²))
• ✅ Approach 2: Optimal Min/Max Tracking (O(N) Time, O(1) Space)
• ✅ Step-by-Step Dry Run
• ✅ Time and Space Complexity Analysis
• ✅ Interview Tips and Common Mistakes

Problem Statement

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: [2, 3] has the largest product 6.

Example 2:

Input: nums = [-2, 0, -1]
Output: 0
Explanation: The result cannot be 2, because [-2, -1] is not a contiguous subarray.

Real-World Analogy

Imagine you are tracking stock portfolio value over several volatile cycles where multipliers can be positive (growth) or negative (losses/shorts).

When your portfolio encounters a negative multiplier:

• Your biggest profit (currentMax) suddenly becomes your biggest loss (currentMin).
• Your biggest loss (currentMin) suddenly becomes your potential biggest profit (currentMax) if another negative multiplier follows!

So, to prepare for future negative multipliers, you must keep track of both your best-case gain and your worst-case loss at every single step.

Important Concepts

Why Negative Numbers Matter

Consider the array:

nums = [2, 3, -2, -4]

At index 0 (2): Max = 2, Min = 2

At index 1 (3): Max = 6, Min = 3

At index 2 (-2):

• Max = Math.max(-2, 6 * -2, 3 * -2) = -2
• Min = Math.min(-2, 6 * -2, 3 * -2) = -12

At index 3 (-4):

• Multiplying by Min (-12): -12 * -4 = 48
• Multiplying by Max (-2): -2 * -4 = 8
• New Max = 48

Notice how the small minimum product (-12) at index 2 transformed into the largest maximum product (48) at index 3.

Core Formula

For any element at index i:

currentMax = Max(nums[i], prevMax * nums[i], prevMin * nums[i])
currentMin = Min(nums[i], prevMax * nums[i], prevMin * nums[i])

Approach 1: Brute Force (Building Intuition)

Before jumping to the optimal solution, let’s look at the naive way to solve this.

Get Onlinecourses’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Check every possible contiguous subarray by using nested loops, computing their products, and tracking the global maximum.

Java Code (Brute Force)

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int maxProduct = nums[0];

        for (int i = 0; i < n; i++) {
            int currentProduct = 1;
            for (int j = i; j < n; j++) {
                currentProduct *= nums[j];
                maxProduct = Math.max(maxProduct, currentProduct);
            }
        }
        return maxProduct;
    }
}

Complexity

• Time Complexity: O(N²) — Two nested loops traversing all subarrays.
• Space Complexity: O(1) extra space.

Approach 2: Min / Max Tracking (Optimal O(N) Time, O(1) Space)

To solve this in linear time, we maintain three variables as we iterate through the array:

1. currentMax: The maximum product ending at the current position.
2. currentMin: The minimum product ending at the current position.
3. globalMax: The maximum product found so far.

When we encounter a negative number, currentMax and currentMin swap roles before calculation.

When we encounter a 0, both currentMax and currentMin reset to 0, effectively starting a new subarray search at the next element.

Algorithm

1. Initialize currentMax = nums[0], currentMin = nums[0], and globalMax = nums[0].
2. Loop i from 1 to N - 1:

• If nums[i] is negative, swap currentMax and currentMin.
• Update currentMax = Math.max(nums[i], currentMax * nums[i]).
• Update currentMin = Math.min(nums[i], currentMin * nums[i]).
• Update globalMax = Math.max(globalMax, currentMax).

3. Return globalMax.

Java Code

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int currentMax = nums[0];
        int currentMin = nums[0];
        int globalMax = nums[0];

        for (int i = 1; i < n; i++) {
            int num = nums[i];

            // If negative, swap currentMax and currentMin
            if (num < 0) {
                int temp = currentMax;
                currentMax = currentMin;
                currentMin = temp;
            }

            // Calculate new max and min ending at current position
            currentMax = Math.max(num, currentMax * num);
            currentMin = Math.min(num, currentMin * num);

            // Update overall answer
            globalMax = Math.max(globalMax, currentMax);
        }

        return globalMax;
    }
}

Complexity Analysis

Time Complexity: O(N)

We traverse the array of length N exactly once. Each step performs basic mathematical operations in O(1) time.

Space Complexity: O(1) Auxiliary Space

Only constant extra space is used for variables (currentMax, currentMin, globalMax, temp).

Interview Tips ⭐

Whenever you see:

• “Find contiguous subarray with maximum product”
• “Array contains negative numbers or zeros”
• “Optimize from O(N²) to O(N)”

Think about:

• Modified Kadane’s Algorithm
• Tracking both Min and Max simultaneously
• Swapping Min and Max when multiplying by a negative number

Common Mistakes

❌ Applying standard Kadane’s directly Standard Kadane’s only tracks currentMax. It forgets currentMin, missing huge positive products formed by multiplying two negative numbers.

❌ Forgetting to swap before calculation If you update currentMax first without saving the old value or swapping, currentMin calculation will incorrectly use the newly calculated currentMax.

❌ Resetting currentMax to 0 or 1 on zero Using Math.max(num, currentMax * num) naturally handles zero values without requiring extra if checks.

💡 Key Takeaway

Negative numbers invert comparison logic in dynamic programming problems involving products.

Remember this golden rule:

• Positive Number ->Keeps Max as Max and Min as Min.
• Negative Number ->Swaps Max and Min.

Conclusion

Maximum Product Subarray looks like a straightforward variation of Kadane’s Algorithm, but handling negative multipliers requires maintaining dual states.

We explored:

• Why standard Kadane’s fails on product problems.
• How to track currentMax and currentMin.
• An optimal solution running in O(N) time and O(1) space.

This article is part of my Blind 75 in Java series.

➡️ Next: Maximum Subarray(LeetCode 53)

If you found this article helpful, consider following me for more beginner-friendly Java interview solutions.

Happy coding! 🚀