Maximum Product Subarray in DSA Java - Execution Trace

Concept Flow - Maximum Product Subarray

Start at index 0

↓

Initialize maxProd, minProd, result

↓

For each element i in array

↓

Calculate temp max and min products

↓

Update maxProd and minProd

↓

Update result if maxProd > result

↓

Move to next element

↓

End of array?

No→Repeat

Yes↓

Return result

We move through the array, keeping track of the maximum and minimum products ending at each position, updating the overall maximum product found.

Execution Sample

DSA Java

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

This code finds the maximum product of any contiguous subarray by tracking max and min products at each step.

Execution Table

Step	Index i	Current Number nums[i]	temp (old maxProd)	maxProd	minProd	result	Explanation
0	0	2	-	2	2	2	Initialize maxProd, minProd, result with nums[0] = 2
1	1	3	2	6	3	6	maxProd = max(3, max(2*3, 2*3))=6; minProd = min(3, min(2*3, 2*3))=3; result updated to 6
2	2	-2	6	-2	-12	6	maxProd = max(-2, max(6*-2, 3*-2)) = -2; minProd = min(-2, min(6*-2, 3*-2)) = -12; result stays 6
3	3	4	-2	4	-48	6	maxProd = max(4, max(-2*4, -12*4))=4; minProd = min(4, min(-2*4, -12*4))=-48; result stays 6
4	4	-1	4	48	-4	48	maxProd = max(-1, max(4*-1, -48*-1))=48; minProd = min(-1, min(4*-1, -48*-1))=-4; result updated to 48
5	5	0	48	0	0	48	maxProd = max(0, max(48*0, -4*0))=0; minProd = min(0, min(48*0, -4*0))=0; result stays 48
6	6	-3	0	0	-3	48	maxProd = max(-3, max(0*-3, 0*-3))=0; minProd = min(-3, min(0*-3, 0*-3))=-3; result stays 48
7	7	1	0	1	-3	48	maxProd = max(1, max(0*1, -3*1))=1; minProd = min(1, min(0*1, -3*1))=-3; result stays 48
8	8	-2	1	6	-2	48	maxProd = max(-2, max(1*-2, -3*-2))=6; minProd = min(-2, min(1*-2, -3*-2))=-2; result stays 48
9	9	4	6	24	-8	48	maxProd = max(4, max(6*4, -2*4))=24; minProd = min(4, min(6*4, -2*4))=-8; result stays 48
10	10	-5	24	40	-120	48	maxProd = max(-5, max(24*-5, -8*-5))=40; minProd = min(-5, min(24*-5, -8*-5))=-120; result stays 48
11	11	2	40	80	-240	80	maxProd = max(2, max(40*2, -120*2))=80; minProd = min(2, min(40*2, -120*2))=-240; result updated to 80
12	-	-	-	-	-	80	End of array reached, return result 80

💡 Reached end of array, final maximum product subarray is 80

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	Final
maxProd	2	6	-2	4	48	0	0	1	6	24	40	80	80
minProd	2	3	-12	-48	-4	0	-3	-3	-2	-8	-120	-240	-240
result	2	6	6	6	48	48	48	48	48	48	48	80	80

Key Moments - 3 Insights

Why do we track both maxProd and minProd at each step?

Because a negative number can turn a small minProd into a large maxProd when multiplied, as seen at step 10 where minProd * nums[i] becomes the new maxProd.

Why do we store maxProd in a temporary variable before updating minProd?

Because minProd calculation depends on the old maxProd value, so we save it in 'temp' to avoid losing it during the update, as shown in step 2.

Why does the result update only when maxProd is greater?

Because maxProd represents the largest product ending at the current index, so only when it exceeds the current result do we update the overall maximum product, as in steps 1, 4, and 11.

Visual Quiz - 3 Questions

Look at the execution table at step 4. What is the value of maxProd?

A -48

B 48

C 4

D -1

💡 Hint

Check the 'maxProd' column at step 4 in the execution_table.

At which step does the result first update to a value greater than 6?

A Step 4

B Step 5

C Step 3

D Step 10

💡 Hint

Look at the 'result' column in the execution_table and find when it changes from 6 to a higher value.

If the input array started with a negative number instead of 2, how would the initial maxProd and minProd values change?

A Both would be zero

B maxProd would be zero, minProd would be the negative number

C Both would be the negative number

D maxProd would be the negative number, minProd would be zero

💡 Hint

Check the initialization step 0 where maxProd and minProd are set to nums[0].

Concept Snapshot

Maximum Product Subarray:
- Track maxProd and minProd at each index
- Update maxProd = max(current, maxProd*current, minProd*current)
- Update minProd = min(current, maxProd*current, minProd*current)
- Keep result as max of maxProd
- Handles negative numbers by tracking minProd
- Return result after full array scan

Full Transcript

The Maximum Product Subarray problem finds the largest product of any contiguous subarray within an array. We start at the first element, setting maxProd, minProd, and result to that value. Then, for each next element, we calculate new maxProd and minProd by considering the current number, the product of maxProd and current number, and the product of minProd and current number. This is because a negative number can flip the smallest product into the largest. We update the result whenever maxProd exceeds it. We continue until the end of the array and return the result. This approach efficiently handles positive, negative, and zero values in the array.

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