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

Recall & Review

beginner

What is the 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

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 while keeping track of max and min products.

intermediate

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.

advanced

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 max product becomes min and min becomes max after multiplication, so swapping helps correctly update these values.

What does the Maximum Product Subarray problem ask you to find?

A The contiguous subarray with the largest product

B The contiguous subarray with the largest sum

C The maximum element in the array

D The minimum product of any subarray

The problem is about finding the contiguous subarray that yields the maximum product.

Why do we track both maximum and minimum products at each step?

A To handle zeros in the array

B To find the maximum sum subarray

C Because negative numbers can flip min to max and vice versa

D To sort the array

Negative numbers can turn a minimum product into a maximum product when multiplied, so tracking both is necessary.

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

A O(n log n)

B O(n)

C O(n^2)

D O(1)

The solution scans the array once, so it runs in linear time O(n).

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

A Ignore it and continue

B Multiply it with the min product

C Multiply it with the max product

D Reset the product calculations starting from the next element

Zero resets the product, so we start fresh from the next element.

When encountering a negative number, why do we swap the max and min products?

A Because the negative number flips max and min after multiplication

B To reset the products

C To sort the products

D To ignore the negative number

Multiplying by a negative number flips the sign, so max becomes min and min becomes max.

Describe the approach to solve the Maximum Product Subarray problem and why tracking both max and min products is important.

Think about how negative numbers affect products.

Explain how zeros and negative numbers affect the calculation of the maximum product subarray.

Consider the sign changes and product resets.

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 sum of its elements

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

D. The subarray with the largest difference between elements

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Compare options with problem goal

   Only The contiguous subarray with the largest product of its elements matches the goal of finding the maximum product of a contiguous subarray.

3. Final Answer:

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

4. Quick Check:

   Maximum product subarray = largest product contiguous segment [OK]

Hint: Look for largest product, not sum or difference [OK]

Common Mistakes:

• Confusing product with sum
• Ignoring the contiguous subarray condition
• Thinking about smallest product instead

2. Which of the following Python code snippets correctly initializes variables to track the maximum product subarray?

easy

A. max_prod = None; min_prod = None; result = None

B. max_prod = 0; min_prod = 0; result = 0

C. max_prod = float('inf'); min_prod = float('-inf'); result = 0

D. max_prod = nums[0]; min_prod = nums[0]; result = nums[0]

Solution

1. Step 1: Understand initialization for max and min products

   We start with the first element as initial max, min, and result because the subarray must include at least one element.

2. Step 2: Check each option's correctness

   max_prod = nums[0]; min_prod = nums[0]; result = nums[0] correctly initializes all three variables to the first element of the array, which is standard practice.

3. Final Answer:

   max_prod = nums[0]; min_prod = nums[0]; result = nums[0] -> Option D

4. Quick Check:

   Initialize with first element to track products [OK]

Hint: Initialize with first element, not zero or None [OK]

Common Mistakes:

• Initializing with zero causes wrong results if array has negatives
• Using None causes errors in multiplication
• Using infinity values breaks logic

3. What is the output of the following code?

def maxProduct(nums):
    max_prod = min_prod = result = nums[0]
    for n in nums[1:]:
        candidates = (n, max_prod * n, min_prod * n)
        max_prod = max(candidates)
        min_prod = min(candidates)
        result = max(result, max_prod)
    return result

print(maxProduct([2,3,-2,4]))

medium

A. 24

B. 6

C. -2

D. 4

Solution

1. Step 1: Trace the loop with input [2,3,-2,4]

   Start: max_prod = min_prod = result = 2 Iteration 1 (n=3): candidates = (3, 2*3=6, 2*3=6) max_prod=6, min_prod=3, result=6 Iteration 2 (n=-2): candidates = (-2, 6*(-2)=-12, 3*(-2)=-6) max_prod=-2, min_prod=-12, result=6 Iteration 3 (n=4): candidates = (4, -2*4=-8, -12*4=-48) max_prod=4, min_prod=-48, result=6

2. Step 2: Determine final result

   The maximum product found during iterations is 6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Maximum product subarray = 6 [OK]

Hint: Track max and min products each step [OK]

Common Mistakes:

• Ignoring min product when negative flips sign
• Only tracking max product causes wrong answer
• Not updating result each iteration

4. Find the error in this code snippet for maximum product subarray:

def maxProduct(nums):
    max_prod = min_prod = result = 0
    for n in nums:
        temp_max = max_prod
        max_prod = max(n, max_prod * n, min_prod * n)
        min_prod = min(n, temp_max * n, min_prod * n)
        result = max(result, max_prod)
    return result

medium

A. Initializing max_prod, min_prod, and result to 0 instead of nums[0]

B. Using temp_max instead of max_prod directly

C. Not iterating from second element

D. Returning result instead of max_prod

Solution

1. Step 1: Check variable initialization

   Initializing max_prod, min_prod, and result to 0 causes errors if all numbers are negative or first element is not zero.

2. Step 2: Compare with correct initialization

   Correct approach initializes these variables to nums[0] to handle negative and positive values properly.

3. Final Answer:

   Initializing max_prod, min_prod, and result to 0 instead of nums[0] -> Option A

4. Quick Check:

   Initialize with first element, not zero [OK]

Hint: Always initialize with first element, not zero [OK]

Common Mistakes:

• Starting max/min product at zero causes wrong results
• Not handling negative numbers properly
• Forgetting to update result each iteration

5. Given the array nums = [1, -2, -3, 0, 7, -8, -2], what is the maximum product of any contiguous subarray?

hard

A. 112

B. 48

C. 7

D. 0

Solution

1. Step 1: Identify subarrays with max product

   Check subarrays: - [1, -2, -3] product = 1 * -2 * -3 = 6 - [7] product = 7 - [7, -8, -2] product = 7 * -8 * -2 = 112 (since -8 * -2 = 16, 7 * 16 = 112) - Others are smaller or zero

2. Step 2: Confirm maximum product

   The largest product found is 112 from subarray [7, -8, -2].

3. Final Answer:

   112 -> Option A

4. Quick Check:

   Max product subarray = 112 [OK]

Hint: Check negative pairs that flip sign to positive [OK]

Common Mistakes:

• Ignoring negative number pairs that increase product
• Stopping at zero without checking after
• Only considering single elements