Maximum Product Subarray in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Maximum Product Subarray problem?

To find the contiguous subarray within an array that has the largest product of its elements.

intermediate

Why do we keep track of both maximum and minimum products at each step in the Maximum Product Subarray problem?

Because a negative number can turn a minimum product into a maximum product when multiplied, so tracking both helps handle negative values correctly.

beginner

In the Maximum Product Subarray problem, what happens when the current element is zero?

The product resets because zero multiplied by anything is zero, so we start fresh from the next element.

beginner

What is the time complexity of the optimal solution for the Maximum Product Subarray problem?

O(n), where n is the number of elements in the array, because we scan the array once.

intermediate

Explain the role of swapping max and min products when encountering a negative number in the Maximum Product Subarray algorithm.

When a negative number is encountered, the maximum product becomes the minimum product times the negative number, and vice versa, so swapping helps correctly update these values.

What do you track at each step to solve the Maximum Product Subarray problem efficiently?

A Number of positive elements

B Only the maximum product so far

C Sum of all elements

D Maximum and minimum products ending at current position

Tracking both maximum and minimum products helps handle negative numbers that can flip the sign of the product.

What should you do when the current element is zero in the Maximum Product Subarray problem?

A Reset the product calculations starting from next element

B Ignore zero and continue multiplying

C Multiply zero with previous max product

D Stop the algorithm

Zero resets the product because any product multiplied by zero is zero, so start fresh after zero.

Why might the minimum product become the maximum product after processing a negative number?

A Because minimum product is always positive

B Because multiplying two negatives makes a positive

C Because negative numbers are ignored

D Because maximum product is reset

Multiplying a negative number by a negative minimum product can produce a larger positive product.

What is the best time complexity to solve the Maximum Product Subarray problem?

A O(n)

B O(n^2)

C O(log n)

D O(n!)

The problem can be solved in one pass through the array, so O(n) time.

Which of these is NOT necessary to track in the Maximum Product Subarray problem?

A Maximum product ending at current index

B Minimum product ending at current index

C Sum of elements in subarray

D Global maximum product found so far

Sum is not relevant; the problem focuses on product, not sum.

Describe the step-by-step approach to solve the Maximum Product Subarray problem.

Think about how negative numbers affect product and why tracking both max and min is important.

Explain why the Maximum Product Subarray problem requires tracking both maximum and minimum products instead of just the maximum.

Consider what happens when multiplying by a negative number.

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