Maximum Product Subarray in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Maximum Product Subarray problem?

To find the contiguous subarray within an array that has the largest product of its elements.

intermediate

Why do we keep track of both maximum and minimum products at each step in the Maximum Product Subarray problem?

Because a negative number can turn a minimum product into a maximum product when multiplied, so tracking both helps handle negative values correctly.

beginner

In the Maximum Product Subarray algorithm, what do the variables max_so_far and min_so_far represent?

max_so_far stores the maximum product ending at the current position, and min_so_far stores the minimum product ending at the current position.

beginner

What is the time complexity of the optimal solution for the Maximum Product Subarray problem?

O(n), where n is the number of elements in the array, because it requires only one pass through the array.

intermediate

How does the algorithm handle zero values in the array when finding the maximum product subarray?

Zero resets the product calculations because any product with zero is zero; the algorithm restarts tracking max and min products from the next element.

What should you track at each step to solve the Maximum Product Subarray problem efficiently?

A Both maximum and minimum products ending at current index

B Only the maximum product so far

C Only the minimum product so far

D Sum of all elements so far

Tracking both maximum and minimum products helps handle negative numbers that can flip the sign of the product.

What is the output of the Maximum Product Subarray for the array [2, 3, -2, 4]?

A -2

B 6

C 4

D 24

The subarray [2, 3] has the maximum product 6.

How does the algorithm handle a negative number in the array?

A It ignores negative numbers

B It only multiplies positive numbers

C It swaps max and min products before multiplying

D It resets the product to zero

Swapping max and min products handles the sign change caused by negative numbers.

What is the time complexity of the Maximum Product Subarray solution?

A O(1)

B O(n log n)

C O(n^2)

D O(n)

The solution iterates through the array once, so it runs in linear time O(n).

What happens when the array contains zero in the Maximum Product Subarray problem?

A The product becomes zero and tracking restarts after zero

B Zero is ignored

C The product becomes maximum

D The algorithm fails

Zero resets the product because multiplying by zero results in zero; tracking restarts after zero.

Explain how to solve the Maximum Product Subarray problem step-by-step.

Think about how negative numbers and zero affect the product.

Describe why tracking both maximum and minimum products is necessary in the Maximum Product Subarray problem.

Consider what happens when multiplying by a negative number.

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