Maximum Product Subarray in DSA C - Execution Trace

Concept Flow - Maximum Product Subarray

Start at first element

↓

Initialize max_prod, min_prod, result

↓

For each element in array

↓

Calculate candidates: current element, max_prod*element, min_prod*element

↓

Update max_prod = max(candidates)

↓

Update min_prod = min(candidates)

↓

Update result = max(result, max_prod)

↓

Repeat for all elements

↓

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 C

int maxProduct(int* nums, int numsSize) {
    int max_prod = nums[0], min_prod = nums[0], result = nums[0];
    for (int i = 1; i < numsSize; i++) {
        int candidates[3] = {nums[i], max_prod * nums[i], min_prod * nums[i]};
        max_prod = candidates[0] > candidates[1] ? candidates[0] : candidates[1];
        max_prod = max_prod > candidates[2] ? max_prod : candidates[2];
        min_prod = candidates[0] < candidates[1] ? candidates[0] : candidates[1];
        min_prod = min_prod < candidates[2] ? min_prod : candidates[2];
        if (max_prod > result) result = max_prod;
    }
    return result;
}

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

Execution Table

Step	Operation	Current Element	Candidates (curr, max_prod*curr, min_prod*curr)	max_prod	min_prod	result	Visual State
0	Initialize	2	[2, -, -]	2	2	2	Array: [2,3,-2,4]
1	Process element	3	[3, 2*3=6, 2*3=6]	6	3	6	Max product subarray ends at index 1: [2,3]
2	Process element	-2	[-2, 6*(-2)=-12, 3*(-2)=-6]	6	-12	6	Max product subarray still [2,3], min_prod updated
3	Process element	4	[4, 6*4=24, -12*4=-48]	24	-48	24	Max product subarray updated to [2,3,-2,4]
4	End	-	-	-	-	24	Final max product is 24

💡 All elements processed, maximum product subarray found

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
max_prod	2	6	6	24	24
min_prod	2	3	-12	-48	-48
result	2	6	6	24	24

Key Moments - 3 Insights

Why do we track both max_prod and min_prod at each step?

Because a negative number can turn a small min_prod into a large max_prod when multiplied, tracking both ensures we don't miss a larger product (see execution_table steps 2 and 3).

Why do we update result only with max_prod and not min_prod?

Result tracks the maximum product found so far, which must be the max_prod at each step, since min_prod is the smallest product and can't be the maximum (see execution_table result column).

What happens when the current element is negative?

max_prod and min_prod swap roles because multiplying by a negative flips signs, so we calculate candidates and pick max and min accordingly (see step 2 and 3 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the value of min_prod?

A -6

B -12

C 3

D -2

💡 Hint

Check the 'min_prod' column at step 2 in execution_table

At which step does the result get updated to 6?

A Step 0

B Step 1

C Step 2

D Step 3

💡 Hint

Look at the 'result' column in execution_table and see when it changes from 2 to 6

If the array started with a negative number, how would max_prod and min_prod initialization change?

A Both start as 0

B max_prod starts as 0, min_prod as negative number

C Both start as the first element, even if negative

D max_prod starts as 1, min_prod as -1

💡 Hint

Check variable_tracker 'Start' values and initialization in code

Concept Snapshot

Maximum Product Subarray:
- Track max_prod and min_prod at each element
- max_prod = max(current, max_prod*current, min_prod*current)
- min_prod = min(current, max_prod*current, min_prod*current)
- Update result with max_prod
- Handles negative numbers by tracking min_prod
- Returns max product of any contiguous subarray

Full Transcript

The Maximum Product Subarray problem finds the largest product of contiguous elements in an array. We keep track of two values at each step: max_prod, the maximum product ending at the current element, and min_prod, the minimum product ending at the current element. This is important because multiplying by a negative number can turn a small min_prod into a large max_prod. We update these values by considering the current element alone, or multiplied by the previous max_prod or min_prod. The overall result is updated with the max_prod at each step. This approach ensures we find the maximum product subarray even when negative numbers are involved.

Practice

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

easy

A. The subarray with the largest difference between elements

B. The contiguous subarray with the largest sum of its elements

C. The subarray with the smallest product of its elements

D. The contiguous subarray with the largest product of its elements

Solution

1. Step 1: Understand the problem and differentiate from similar problems

   The problem asks for a contiguous part of the array where the product of all elements is the highest possible. Unlike maximum sum subarray, this problem focuses on product, which can be affected by negative numbers and zeros.

2. Final Answer:

   The contiguous subarray with the largest product of its elements -> Option D

3. Quick Check:

   Maximum product subarray = largest product subarray [OK]

Hint: Focus on product, not sum, for this problem [OK]

Common Mistakes:

• Confusing product with sum
• Ignoring negative numbers impact
• Thinking subarray can be non-contiguous

2. Which of the following is the correct way to declare variables to track the maximum and minimum products at each step in C for the Maximum Product Subarray problem?

easy

A. int maxProd = 1, minProd = 1;

B. int maxProd, minProd = 0;

C. int maxProd = 0, minProd = 0;

D. int maxProd = -1, minProd = -1;

Solution

1. Step 1: Initialize maxProd and minProd properly and check alternatives

   Both maxProd and minProd should start at 1 because multiplying by 1 does not change the product. Other initializations use zero (nullifies products), negative values, or leave variables uninitialized leading to incorrect calculations or undefined behavior.

2. Final Answer:

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

3. Quick Check:

   Initialize maxProd and minProd to 1 [OK]

Hint: Start max and min product as 1 to avoid zero multiplication [OK]

Common Mistakes:

• Initializing maxProd or minProd to 0
• Not initializing both variables
• Using negative initial values

3. What is the output of the following C code snippet for the array int arr[] = {2, 3, -2, 4};?

int maxProductSubarray(int* nums, int numsSize) {
    int maxProd = nums[0], minProd = nums[0], result = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] < 0) {
            int temp = maxProd;
            maxProd = minProd;
            minProd = temp;
        }
        maxProd = (nums[i] > maxProd * nums[i]) ? nums[i] : maxProd * nums[i];
        minProd = (nums[i] < minProd * nums[i]) ? nums[i] : minProd * nums[i];
        if (maxProd > result) result = maxProd;
    }
    return result;
}

int main() {
    int arr[] = {2, 3, -2, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("%d", maxProductSubarray(arr, size));
    return 0;
}

medium

A. 4

B. 6

C. -2

D. 24

Solution

1. Step 1: Trace the loop and determine final result

   Start with maxProd=2, minProd=2, result=2. - i=1 (3): maxProd=max(3,2*3)=6, minProd=min(3,2*3)=3, result=6 - i=2 (-2): swap to maxProd=3, minProd=6; maxProd=max(-2,3*(-2))=-2, minProd=min(-2,6*(-2))=-12, result=6 - i=3 (4): maxProd=max(4,-2*4)=4, minProd=min(4,-12*4)=-48, result=6 The maximum product found is 6 from subarray [2,3].

2. Final Answer:

   6 -> Option B

3. Quick Check:

   Max product subarray = 6 [OK]

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

Common Mistakes:

• Not swapping max and min on negative number
• Confusing max product with sum
• Incorrectly updating result

4. Identify the bug in the following C code snippet for Maximum Product Subarray and select the correct fix:

int maxProductSubarray(int* nums, int numsSize) {
    int maxProd = 1, minProd = 1, result = nums[0];
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < 0) {
            int temp = maxProd;
            maxProd = minProd;
            minProd = temp;
        }
        maxProd = (nums[i] > maxProd * nums[i]) ? nums[i] : maxProd * nums[i];
        minProd = (nums[i] < minProd * nums[i]) ? nums[i] : minProd * nums[i];
        if (maxProd > result) result = maxProd;
    }
    return result;
}

medium

A. Initialize maxProd and minProd with nums[0] and start loop from i=1

B. Remove the swap of maxProd and minProd when nums[i] < 0

C. Initialize result to 1 instead of nums[0]

D. Change the loop to run from i=1 to numsSize-1 without other changes

Solution

1. Step 1: Check initialization and loop start; analyze other options

   maxProd and minProd should start as nums[0] to correctly handle the first element. Loop should start from i=1 to avoid reprocessing first element. Removing swap breaks handling of negative numbers. Initializing result to 1 is incorrect if nums[0] is negative. Changing loop start without fixing initialization causes errors.

2. Final Answer:

   Initialize maxProd and minProd with nums[0] and start loop from i=1 -> Option A

3. Quick Check:

   Proper initialization and loop start fix bug [OK]

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

Common Mistakes:

• Starting loop from 0 with maxProd=1
• Not swapping max and min on negative
• 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. 1800

B. 0

C. 60

D. -1

Solution

1. Step 1: Analyze subarrays and their products

   Relevant products: [60]=60, [-3,-10]=30, [-1,-3]=3, [-1,-3,-10]=-30, [-10]=-10, subarrays crossing or including 0=0. No larger contiguous product exists (e.g. [-3,-10,60] skips 0, invalid).

2. Final Answer:

   60 -> Option C

3. Quick Check:

   Max product subarray = 60 [OK]

Hint: Check negative pairs and zeros carefully [OK]

Common Mistakes:

• Thinking non-contiguous subarrays like [-3,-10,60] are valid
• Choosing [-3,-10]=30 instead of 60
• Confusing zero as max product