Maximum Product Subarray in DSA C++ - Execution Trace

Concept Flow - Maximum Product Subarray

Start at index 0

↓

Initialize max_prod, min_prod, result

↓

For each element i in array

↓

If element < 0, swap max_prod and min_prod

↓

Update max_prod = max(element, max_prod * element)

↓

Update min_prod = min(element, min_prod * element)

↓

Update result = max(result, max_prod)

↓

Move to next element

Back to For loop↓

Return result

↩Back to For loop

We scan the array once, keeping track of the maximum and minimum products ending at each position, swapping them when a negative number appears, and update the result with the maximum product found.

Execution Sample

DSA C++

int maxProduct(vector<int>& nums) {
    int max_prod = nums[0], min_prod = nums[0], result = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] < 0) swap(max_prod, min_prod);
        max_prod = max(nums[i], max_prod * nums[i]);
        min_prod = min(nums[i], min_prod * nums[i]);
        result = max(result, max_prod);
    }
    return result;
}

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

Execution Table

Step	Index	Current Element	Swap max_prod & min_prod?	max_prod	min_prod	result	Explanation
0	0	2	No	2	2	2	Initialize max_prod, min_prod, result to first element 2
1	1	3	No	6	3	6	max_prod = max(3, 2*3)=6; min_prod = min(3, 2*3)=3; result updated to 6
2	2	-2	Yes	-2	-12	6	Element negative, swap max_prod and min_prod; max_prod = max(-2, 3*-2)=-2; min_prod = min(-2, 6*-2)=-12; result stays 6
3	3	4	No	4	-48	6	max_prod = max(4, -2*4)=4; min_prod = min(4, -12*4)=-48; result stays 6
4	4	-1	Yes	48	-4	48	Element negative, swap max_prod and min_prod; max_prod = max(-1, -48*-1)=48; min_prod = min(-1, 4*-1)=-4; result updated to 48
5	5	0	No	0	0	48	max_prod = max(0, 48*0)=0; min_prod = min(0, -4*0)=0; result stays 48
6	6	5	No	5	0	48	max_prod = max(5, 0*5)=5; min_prod = min(5, 0*5)=0; result stays 48
7	7	-3	Yes	0	-15	48	Element negative, swap max_prod and min_prod; max_prod = max(-3, 0*-3)=0; min_prod = min(-3, 5*-3)=-15; result stays 48
8	8	1	No	1	-15	48	max_prod = max(1, 0*1)=1; min_prod = min(1, -15*1)=-15; result stays 48
End	-	-	-	-	-	48	Reached end of array, final result is 48

💡 Reached end of array, no more elements to process

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
max_prod	2	6	-2	4	48	0	5	0	1	1
min_prod	2	3	-12	-48	-4	0	0	-15	-15	-15
result	2	6	6	6	48	48	48	48	48	48

Key Moments - 3 Insights

Why do we swap max_prod and min_prod when the current element is negative?

Because multiplying by a negative flips the sign, the previous max_prod could become the new min_prod and vice versa. This is shown at steps 2, 4, and 7 in the execution_table where swap happens before updating max_prod and min_prod.

Why do we track both max_prod and min_prod instead of just max_prod?

Because a minimum product (negative) can become maximum if multiplied by a negative number later. Tracking both ensures we don't miss a larger product. See step 4 where min_prod is -48 but after multiplying by -1 it helps get max_prod 48.

Why does the result not always update at every step?

Result updates only when max_prod is greater than current result. For example, at step 3 max_prod is 4 but result is 6, so result stays 6. This prevents lowering the maximum product found so far.

Visual Quiz - 3 Questions

Look at the execution_table, what is max_prod at step 4?

A 48

B -2

C 4

D -48

💡 Hint

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

At which step does the condition to swap max_prod and min_prod first occur?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look for 'Yes' in the 'Swap max_prod & min_prod?' column in execution_table.

If the array had no negative numbers, how would the swap step change?

A Swap would never happen

B Swap would happen every step

C Swap would happen only at the first step

D Swap would happen only at the last step

💡 Hint

Refer to the swap condition in the execution_table where swap happens only if current element is negative.

Concept Snapshot

Maximum Product Subarray:
- Track max_prod and min_prod at each index
- Swap max_prod and min_prod if current element < 0
- Update max_prod = max(current element, max_prod * current element)
- Update min_prod = min(current element, min_prod * current element)
- Keep result as max of max_prod
- Single pass, O(n) time, O(1) space

Full Transcript

The Maximum Product Subarray problem finds the largest product of any contiguous subarray. We scan the array once, keeping track of two values at each step: max_prod (maximum product ending here) and min_prod (minimum product ending here). When we see a negative number, we swap max_prod and min_prod because multiplying by a negative flips signs. Then we update max_prod and min_prod by comparing the current element alone and the product with previous max or min. We keep updating the result with the largest max_prod found. This approach handles negative numbers and zeros efficiently in one pass.

Practice

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

easy

A. The subarray with the smallest product 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 maximum sum of its elements

Solution

1. Step 1: Understand the problem statement

   The problem asks for a contiguous part of the array where the product of all numbers is the highest possible.

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 contiguous subarray with max multiplication, not sum [OK]

Common Mistakes:

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

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

easy

A. int maxProd = 1, minProd = INT_MIN;

B. int maxProd = 0, minProd = 0;

C. int maxProd = INT_MIN, minProd = INT_MAX;

D. int maxProd = 1, minProd = 1;

Solution

1. Step 1: Understand initialization role

   We start with 1 because multiplying by 1 doesn't change product; it acts as neutral.

2. Step 2: Check each option

   int maxProd = 1, minProd = 1; uses 1 for both maxProd and minProd, which is correct for product tracking.

3. Final Answer:

   int maxProd = 1, minProd = 1; -> Option D

4. Quick Check:

   Initialize maxProd and minProd to 1 [OK]

Hint: Initialize max and min product as 1 to start multiplication [OK]

Common Mistakes:

• Using 0 which resets product
• Using INT_MIN or INT_MAX incorrectly
• Not initializing min product

3. What is the output of the following C++ code snippet?

int arr[] = {2, 3, -2, 4};
int n = 4;
int maxProd = arr[0], minProd = arr[0], result = arr[0];
for (int i = 1; i < n; i++) {
    if (arr[i] < 0) std::swap(maxProd, minProd);
    maxProd = std::max(arr[i], maxProd * arr[i]);
    minProd = std::min(arr[i], minProd * arr[i]);
    result = std::max(result, maxProd);
}
std::cout << result << std::endl;

medium

A. 6

B. 4

C. -2

D. 8

Solution

1. Step 1: Trace the loop iterations

   Start with maxProd=2, minProd=2, result=2. - i=1 (3): arr[i]=3 >0, no swap maxProd = max(3, 2*3)=6 minProd = min(3, 2*3)=3 result = max(2,6)=6 - i=2 (-2): arr[i]<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 - i=3 (4): arr[i]=4 >0, no swap 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: Determine final result

   The maximum product found is 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Maximum product subarray = 6 [OK]

Hint: Swap max and min when negative number appears [OK]

Common Mistakes:

• Not swapping max and min on negative
• Confusing max and min updates
• Ignoring initial values

4. Identify the bug in this C++ code snippet for Maximum Product Subarray:

int maxProduct(int arr[], int n) {
    int maxProd = 1, minProd = 1, result = 1;
    for (int i = 0; i < n; i++) {
        if (arr[i] < 0) std::swap(maxProd, minProd);
        maxProd = std::max(arr[i], maxProd * arr[i]);
        minProd = std::min(arr[i], minProd * arr[i]);
        result = std::max(result, maxProd);
    }
    return result;
}

medium

A. maxProd and minProd should be initialized to 0

B. Swapping maxProd and minProd should happen after updating them

C. Starting loop from i=0 causes incorrect initial values

D. Result should be initialized to INT_MIN

Solution

1. Step 1: Analyze loop start and initial values

   Starting loop at i=0 uses maxProd=1 and minProd=1 before processing first element, which can cause wrong product calculations.

2. Step 2: Correct approach for initialization and loop

   Initialize maxProd, minProd, and result to arr[0] and start loop from i=1 to correctly track products.

3. Final Answer:

   Starting loop from i=0 causes incorrect initial values -> Option C

4. Quick Check:

   Loop should start at 1 with initial values from arr[0] [OK]

Hint: Initialize with first element, start loop from second element [OK]

Common Mistakes:

• Loop starting at 0 with default initial values
• Swapping max and min at wrong time
• Wrong initialization of result

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

hard

A. 60

B. 180

C. 0

D. -1

Solution

1. Step 1: Analyze subarrays and their products

   Check products of contiguous subarrays: - [-1] = -1 - [-1, -3] = 3 - [-1, -3, -10] = 30 - [-3, -10] = 30 - [-3, -10, 0] = 0 - [0, 60] = 0 - [60] = 60 - [-1, -3, -10, 0, 60] = 0 The maximum product is 30 from subarray [-1, -3, -10].

2. Step 2: Check if any larger product exists

   Although 60 is a single element, the product 30 from three negatives is smaller. The maximum product is 30, but 180 is possible if we consider [-3, -10, 0, 60] incorrectly. Actually, the maximum product is 60 from [60]. However, the product of [-1, -3, -10] is 30, not 180. The option 180 is incorrect as no contiguous subarray produces 180.

3. Final Answer:

   60 -> Option A

4. Quick Check:

   Max product subarray = 60 [OK]

Hint: Multiply negatives carefully; zero resets product [OK]

Common Mistakes:

• Ignoring zero breaks subarray
• Multiplying across zero incorrectly
• Not considering negative number pairs