Maximum Product Subarray in DSA Java

Mental Model

We want to find the largest product of a continuous part of the array. Because negative numbers can flip the sign, we keep track of both the biggest and smallest products so far.

Analogy: Imagine walking on a path where stepping on a slippery stone (negative number) can flip your direction. To reach the farthest point forward (maximum product), you remember both your farthest forward and farthest backward steps because a backward step might help you jump forward later.

Array: [2] -> [-3] -> [4] -> [-1] -> [0] -> [5]
maxProd ↑ 2
minProd ↑ 2
result ↑ 2

Dry Run Walkthrough

Input: array: [2, -3, 4, -1, 0, 5]

Goal: Find the maximum product of any continuous subarray

Step 1: Start with first element: maxProd = 2, minProd = 2, result = 2

maxProd=2, minProd=2, result=2

Why: Initialize with first element to start tracking products

Step 2: Process -3: swap maxProd and minProd because -3 is negative

maxProd=2, minProd=2 (before swap)
After swap: maxProd=2, minProd=2

Why: Negative flips max and min, so swap to keep correct tracking

Step 3: Update maxProd = max(-3, 2 * -3) = max(-3, -6) = -3; minProd = min(-3, 2 * -3) = min(-3, -6) = -6

maxProd=-3, minProd=-6, result=2

Why: Calculate new max and min products including current element

Step 4: Update result = max(2, -3) = 2

result=2

Why: Keep track of the highest product found so far

Step 5: Process 4: maxProd = max(4, -3 * 4) = max(4, -12) = 4; minProd = min(4, -6 * 4) = min(4, -24) = -24

maxProd=4, minProd=-24, result=2

Why: Update max and min products with current element

Step 6: Update result = max(2, 4) = 4

result=4

Why: Update maximum product found

Step 7: Process -1: swap maxProd and minProd because -1 is negative

Before swap: maxProd=4, minProd=-24
After swap: maxProd=-24, minProd=4

Why: Negative flips max and min, so swap

Step 8: Update maxProd = max(-1, -24 * -1) = max(-1, 24) = 24; minProd = min(-1, 4 * -1) = min(-1, -4) = -4

maxProd=24, minProd=-4, result=4

Why: Calculate new max and min products including current element

Step 9: Update result = max(4, 24) = 24

result=24

Why: Update maximum product found

Step 10: Process 0: maxProd = max(0, 24 * 0) = 0; minProd = min(0, -4 * 0) = 0

maxProd=0, minProd=0, result=24

Why: Zero resets product, start fresh from next element

Step 11: Update result = max(24, 0) = 24

result=24

Why: Maximum product remains unchanged

Step 12: Process 5: maxProd = max(5, 0 * 5) = 5; minProd = min(5, 0 * 5) = 0

maxProd=5, minProd=0, result=24

Why: Start new product subarray from 5

Step 13: Update result = max(24, 5) = 24

result=24

Why: Maximum product remains 24

Result:

Maximum product subarray = 24

Annotated Code

DSA Java

public class MaxProductSubarray {
    public static int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int maxProd = nums[0];
        int minProd = nums[0];
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = maxProd;
                maxProd = minProd;
                minProd = temp;
            }
            maxProd = Math.max(nums[i], maxProd * nums[i]);
            minProd = Math.min(nums[i], minProd * nums[i]);
            result = Math.max(result, maxProd);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2, -3, 4, -1, 0, 5};
        System.out.println("Maximum product subarray = " + maxProduct(nums));
    }
}

if (nums[i] < 0) { int temp = maxProd; maxProd = minProd; minProd = temp; }

Swap max and min products when current number is negative to handle sign flip

maxProd = Math.max(nums[i], maxProd * nums[i]);

Update max product ending at current position

minProd = Math.min(nums[i], minProd * nums[i]);

Update min product ending at current position to track potential flip

result = Math.max(result, maxProd);

Update global maximum product found so far

Output

Maximum product subarray = 24

Complexity Analysis

Time: O(n) because we scan the array once, updating max and min products at each step

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Compared to checking all subarrays (O(n^2)), this approach is much faster and efficient

Edge Cases

Empty array

Returns 0 as no subarray exists

DSA Java

if (nums == null || nums.length == 0) return 0;

Array with one element

Returns that element as max product

DSA Java

int maxProd = nums[0]; int minProd = nums[0]; int result = nums[0];

Array with zeros

Zeros reset product calculation, starting fresh after zero

DSA Java

maxProd = Math.max(nums[i], maxProd * nums[i]);

When to Use This Pattern

When asked to find the maximum product of a continuous subarray and negatives can flip signs, use the max/min product tracking pattern to handle sign changes efficiently.

Common Mistakes

Mistake: Not swapping max and min products when encountering a negative number
Fix: Add a swap of maxProd and minProd before updating them when current number is negative

Mistake: Only tracking max product and ignoring min product
Fix: Track both max and min products to handle negative numbers flipping the sign

Summary

Finds the maximum product of any continuous subarray in an array.

Use when you need the largest product subarray and the array contains negative numbers and zeros.

Keep track of both maximum and minimum products at each step to handle sign flips caused by negatives.

Practice

1. What does the Maximum Product Subarray problem ask you to find in an integer array?

easy

A. The contiguous subarray with the largest sum of its elements

B. The contiguous subarray with the largest product of its elements

C. The longest subarray with all positive numbers

D. The subarray with the smallest product of its elements

Solution

1. Step 1: Understand the problem statement

   The problem asks for the contiguous subarray within an array that has the maximum product of its elements.

2. Step 2: Differentiate from similar problems

   This is different from maximum sum subarray; here we multiply elements, not add.

3. Final Answer:

   The contiguous subarray with the largest product of its elements -> Option B

4. Quick Check:

   Maximum Product Subarray = Largest product subarray [OK]

Hint: Look for product, not sum, in contiguous subarrays [OK]

Common Mistakes:

• Confusing product with sum
• Ignoring negative numbers impact
• Assuming non-contiguous subarrays

2. Which of the following Java code snippets correctly initializes variables to track the maximum and minimum products for the Maximum Product Subarray problem?

easy

A. int maxProd = 1, minProd = 1; int result = 0;

B. int maxProd = 0, minProd = 0; int result = 0;

C. int maxProd = Integer.MIN_VALUE, minProd = Integer.MAX_VALUE; int result = 1;

D. int maxProd = 1, minProd = 1; int result = Integer.MIN_VALUE;

Solution

1. Step 1: Identify correct initial values for tracking products

   We start maxProd and minProd at 1 because multiplying by 1 doesn't change the product. Result starts at smallest integer to update correctly.

2. Step 2: Check each option's initialization

   int maxProd = 1, minProd = 1; int result = Integer.MIN_VALUE; correctly initializes maxProd and minProd to 1 and result to Integer.MIN_VALUE for proper comparison.

3. Final Answer:

   int maxProd = 1, minProd = 1; int result = Integer.MIN_VALUE; -> Option D

4. Quick Check:

   Initialize maxProd and minProd to 1, result to min int [OK]

Hint: Initialize max/min product to 1, result to smallest int [OK]

Common Mistakes:

• Initializing max/min product to 0 causes wrong multiplication
• Setting result to 0 misses negative max products
• Using maxProd = Integer.MIN_VALUE breaks multiplication logic

3. What is the output of the following Java code snippet for the array int[] nums = {2, 3, -2, 4};?

int maxProd = 1, minProd = 1, result = Integer.MIN_VALUE;
for (int num : nums) {
    if (num < 0) {
        int temp = maxProd;
        maxProd = minProd;
        minProd = temp;
    }
    maxProd = Math.max(num, maxProd * num);
    minProd = Math.min(num, minProd * num);
    result = Math.max(result, maxProd);
}
System.out.println(result);

medium

A. 4

B. 8

C. 6

D. -2

Solution

1. Step 1: Trace the loop for each element

   Start: maxProd=1, minProd=1, result=Integer.MIN_VALUE - num=2: maxProd=max(2,1*2)=2, minProd=min(2,1*2)=2, result=max(MIN_VALUE,2)=2 - num=3: maxProd=max(3,2*3)=6, minProd=min(3,2*3)=3, result=max(2,6)=6 - num=-2: num<0 swap maxProd and minProd: maxProd=3, minProd=6 maxProd=max(-2,3*(-2))=max(-2,-6)=-2 minProd=min(-2,6*(-2))=min(-2,-12)=-12 result=max(6,-2)=6 - num=4: maxProd=max(4,-2*4)=max(4,-8)=4 minProd=min(4,-12*4)=min(4,-48)=-48 result=max(6,4)=6

2. Step 2: Final result after loop

   The maximum product found is 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Max product subarray = 2*3 = 6 [OK]

Hint: Swap max/min on negative, track max product each step [OK]

Common Mistakes:

• Not swapping max and min on negative number
• Confusing max and min updates
• Forgetting to update result each iteration

4. Identify the bug in this Java code snippet for Maximum Product Subarray and select the correct fix:

int maxProd = 1, minProd = 1, result = Integer.MIN_VALUE;
for (int num : nums) {
    if (num <= 0) {
        int temp = maxProd;
        maxProd = minProd;
        minProd = temp;
    }
    maxProd = Math.max(num, maxProd * num);
    minProd = Math.min(num, minProd * num);
    result = Math.max(result, maxProd);
}

medium

A. Change condition to num < 0 instead of num <= 0

B. Initialize maxProd and minProd to 0 instead of 1

C. Remove swapping maxProd and minProd

D. Update result only after the loop

Solution

1. Step 1: Analyze the condition for swapping maxProd and minProd

   The swap is needed only when the current number is negative because multiplying by a negative flips max and min.

2. Step 2: Identify why <= 0 causes error

   When num is zero, swapping maxProd and minProd is incorrect and breaks logic. So condition should be strictly < 0.

3. Final Answer:

   Change condition to num < 0 instead of num <= 0 -> Option A

4. Quick Check:

   Swap only on negative numbers [OK]

Hint: Swap max/min only when number is negative, not zero [OK]

Common Mistakes:

• Swapping on zero causes wrong product calculations
• Not swapping at all misses negative impact
• Updating result outside loop misses intermediate max

5. Given the array int[] nums = {-1, -3, -10, 0, 60};, what is the maximum product of any contiguous subarray?

hard

A. 60

B. 1800

C. 0

D. -1

Solution

1. Step 1: Consider subarrays and their products

   Check subarrays: - [-1] = -1 - [-1, -3] = 3 - [-1, -3, -10] = -30 - [-3, -10] = 30 - [-3, -10, 0] = 0 - [0, 60] = 0*60=0 - [60] = 60 - [-1, -3, -10, 0, 60] = 0 - [-3, -10, 0, 60] = 0 - [-10, 0, 60] = 0 - [-1, -3, -10, 0] = 0

2. Step 2: Identify maximum product subarray

   Notice [-3, -10, 0, 60] includes zero, product zero. But [-1, -3, -10] product is -1 * -3 * -10 = -30 (negative). Check [-3, -10] = 30 (positive). Check [-1, -3] = 3. Check [-3, -10, 0, 60] zero product. Check [0, 60] = 0. Check [60] = 60. Check [-1, -3, -10, 0, 60] = 0. But what about [-1, -3, -10]? Actually, the product is -1 * -3 * -10 = -1 * 30 = -30 (negative). So max product is 60. But what about [-1, -3, -10, 0, 60]? Zero breaks subarray, so max product subarray is either before or after zero. So max product is 60.

3. Step 3: Reconsider negative products with even count

   Wait, the product of [-1, -3, -10] is -1 * -3 * -10 = -1 * 30 = -30 (negative). But what about [-1, -3, -10, 0, 60]? Zero breaks subarray. Check [-1, -3, -10] product is negative. Check [-3, -10] product is 30. Check [-1, -3] product is 3. Check [60] product is 60. So max product is 60. But what about [-1, -3, -10, 0, 60]? Zero breaks subarray. So max product is 60.

4. Step 4: Final check with code logic

   Using code logic: - Start maxProd=1, minProd=1, result=Integer.MIN_VALUE - num=-1: num<0 swap maxProd and minProd: maxProd=1, minProd=1 maxProd=max(-1,1*-1)=-1 minProd=min(-1,1*-1)=-1 result=max(MIN_VALUE,-1)=-1 - num=-3: num<0 swap maxProd and minProd: maxProd=-1, minProd=-1 maxProd=max(-3,-1*-3)=max(-3,3)=3 minProd=min(-3,-1*-3)=min(-3,3)=-3 result=max(-1,3)=3 - num=-10: num<0 swap maxProd and minProd: maxProd=-3, minProd=3 maxProd=max(-10,-3*-10)=max(-10,30)=30 minProd=min(-10,3*-10)=min(-10,-30)=-30 result=max(3,30)=30 - num=0: num not <0 no swap maxProd=max(0,30*0)=max(0,0)=0 minProd=min(0,-30*0)=min(0,0)=0 result=max(30,0)=30 - num=60: num not <0 no swap maxProd=max(60,0*60)=max(60,0)=60 minProd=min(60,0*60)=min(60,0)=0 result=max(30,60)=60 Final result is 60.

5. Final Answer:

   60 -> Option A

6. Quick Check:

   Maximum product subarray = 60 [OK]

Hint: Track max/min product carefully through negatives and zeros [OK]

Common Mistakes:

• Assuming product of all negatives is always max
• Ignoring zero breaks subarray
• Not updating max/min product correctly after zero