Maximum Product Subarray in DSA Java - Build from Scratch

Maximum Product Subarray

📖 Scenario: Imagine you are analyzing daily sales growth rates of a product over a week. Each day's growth rate can be positive (growth), negative (decline), or zero (no change). You want to find the period (contiguous days) where the product of growth rates is the highest, indicating the best stretch of sales performance.

🎯 Goal: Build a Java program that finds the maximum product of a contiguous subarray within an array of integers representing daily growth rates.

📋 What You'll Learn

Create an integer array called growthRates with the exact values: {2, 3, -2, 4}

Create two integer variables called maxProduct and minProduct and initialize both to the first element of growthRates

Use a for loop with variable i starting from 1 to iterate over growthRates

Inside the loop, update maxProduct and minProduct to track the maximum and minimum products ending at the current index

Create an integer variable called result initialized to the first element of growthRates

Update result inside the loop to keep the maximum product found so far

Print the value of result after the loop ends

💡 Why This Matters

🌍 Real World

Finding the best period of growth in sales or stock prices by analyzing daily percentage changes.

💼 Career

This algorithm is useful in finance, data analysis, and software engineering roles where understanding trends and optimizing performance is important.

1

Create the growth rates array

Create an integer array called growthRates with these exact values: {2, 3, -2, 4}

DSA Java

// Create the growthRates array with values {2, 3, -2, 4}
// Your code here

Hint

Use int[] growthRates = {2, 3, -2, 4}; to create the array.

2

Initialize maxProduct, minProduct, and result

Create three integer variables called maxProduct, minProduct, and result and initialize all to the first element of growthRates

DSA Java

public class MaxProductSubarray {
    public static void main(String[] args) {
        int[] growthRates = {2, 3, -2, 4};
        // Initialize maxProduct, minProduct, and result to growthRates[0]
        // Your code here
    }
}

Hint

Set maxProduct, minProduct, and result to growthRates[0].

3

Implement the loop to find max product subarray

Use a for loop with variable i starting from 1 to iterate over growthRates. Inside the loop, create an integer tempMax to store the current maxProduct. Update maxProduct to the maximum of growthRates[i], maxProduct * growthRates[i], and minProduct * growthRates[i]. Update minProduct to the minimum of growthRates[i], tempMax * growthRates[i], and minProduct * growthRates[i]. Update result to the maximum of result and maxProduct.

DSA Java

public class MaxProductSubarray {
    public static void main(String[] args) {
        int[] growthRates = {2, 3, -2, 4};
        int maxProduct = growthRates[0];
        int minProduct = growthRates[0];
        int result = growthRates[0];
        // Use a for loop from i=1 to growthRates.length
        // Inside loop, update maxProduct, minProduct, and result
        // Your code here
    }
}

Hint

Remember to store the old maxProduct in tempMax before updating it.

4

Print the maximum product result

Print the value of result after the loop ends using System.out.println(result);

DSA Java

public class MaxProductSubarray {
    public static void main(String[] args) {
        int[] growthRates = {2, 3, -2, 4};
        int maxProduct = growthRates[0];
        int minProduct = growthRates[0];
        int result = growthRates[0];
        for (int i = 1; i < growthRates.length; i++) {
            int tempMax = maxProduct;
            maxProduct = Math.max(growthRates[i], Math.max(maxProduct * growthRates[i], minProduct * growthRates[i]));
            minProduct = Math.min(growthRates[i], Math.min(tempMax * growthRates[i], minProduct * growthRates[i]));
            result = Math.max(result, maxProduct);
        }
        // Print the result
        // Your code here
    }
}

Hint

Use System.out.println(result); to display the maximum product.

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