Maximum Product Subarray in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Product Subarray Calculation

What is the output of the following Java code that finds the maximum product of a contiguous subarray?

DSA Java

public class Solution {
    public static int maxProduct(int[] nums) {
        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, -2, 4};
        System.out.println(maxProduct(nums));
    }
}

A 6

B -2

C 4

D 8

💡 Hint

Think about how negative numbers affect the product and how swapping max and min helps.

The maximum product subarray is [2, 3] with product 6. The code tracks max and min products to handle negatives.

❓ Predict Output

intermediate

Maximum Product Subarray Output with Negative Numbers

What is the output of this Java code for the maximum product subarray?

DSA Java

public class Solution {
    public static int maxProduct(int[] nums) {
        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, 0, -1};
        System.out.println(maxProduct(nums));
    }
}

A -2

B -1

C 2

D 0

💡 Hint

Zero resets the product, consider subarrays around zero.

The maximum product subarray is [0] with product 0. Negative numbers and zero reset the product.

🧠 Conceptual

advanced

Why Swap maxProd and minProd When Encountering Negative Number?

In the maximum product subarray algorithm, why do we swap the maxProd and minProd variables when the current number is negative?

A Because swapping resets the product to zero.

B Because multiplying by a negative number reverses max and min, so swapping keeps track of correct extremes.

C Because it sorts the array to handle negatives first.

D Because negative numbers should be ignored in product calculations.

💡 Hint

Think about how multiplying by a negative flips signs.

Multiplying by a negative flips the sign, so the max product could become min and vice versa. Swapping helps track this.

❓ Predict Output

advanced

Output of Maximum Product Subarray with All Negative Numbers

What is the output of this Java code for the maximum product subarray when all numbers are negative?

DSA Java

public class Solution {
    public static int maxProduct(int[] nums) {
        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, -7};
        System.out.println(maxProduct(nums));
    }
}

A 21

B -2

C -42

D 7

💡 Hint

Consider that multiplying two negatives makes a positive.

The maximum product subarray is [-3, -7] with product 21.

🔧 Debug

expert

Identify the Error in Maximum Product Subarray Implementation

What error will this Java code produce when run?

DSA Java

public class Solution {
    public static int maxProduct(int[] nums) {
        int maxProd = 1;
        int minProd = 1;
        int result = Integer.MIN_VALUE;
        for (int i = 0; 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, -2, 4};
        System.out.println(maxProduct(nums));
    }
}

A NullPointerException

B ArithmeticException

C ArrayIndexOutOfBoundsException

D No error, outputs 6

💡 Hint

Check the loop condition carefully.

The loop runs with i <= nums.length, which accesses an invalid index causing ArrayIndexOutOfBoundsException.

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