Maximum Product Subarray in DSA C++

Mental Model

We want to find the largest product of a continuous part of the list. Because multiplying by a negative number flips signs, we keep track of both the biggest and smallest products so far.

Analogy: Imagine walking on a path where stepping on a slippery stone (negative number) can flip your direction. To reach the farthest point forward (maximum product), you remember both how far you went forward and backward, so you can use a backward step to jump forward later.

Array: [2] -> [-3] -> [4] -> [-1] -> [0] -> [5]
Track max_prod and min_prod at each step to find max overall.

Dry Run Walkthrough

Input: array: [2, -3, 4, -1, 0, 5]

Goal: Find the maximum product of any continuous subarray

Step 1: Initialize max_prod, min_prod, and result to first element 2

max_prod=2, min_prod=2, result=2

Why: Start tracking from the first element

Step 2: Process -3: multiply max_prod and min_prod by -3, swap if negative

max_prod = max(-3, 2*-3, 2*-3) = -3
min_prod = min(-3, 2*-3, 2*-3) = -6
result = max(2, -3) = 2

Why: Negative flips max and min, so track both

Step 3: Process 4: multiply max_prod and min_prod by 4

max_prod = max(4, -3*4, -6*4) = 4
min_prod = min(4, -3*4, -6*4) = -24
result = max(2, 4) = 4

Why: 4 can start new subarray or extend previous

Step 4: Process -1: multiply max_prod and min_prod by -1, swap if negative

max_prod = max(-1, 4*-1, -24*-1) = 24
min_prod = min(-1, 4*-1, -24*-1) = -4
result = max(4, 24) = 24

Why: Negative flips max and min, so max becomes 24

Step 5: Process 0: reset max_prod and min_prod to 0

max_prod = max(0, 24*0, -4*0) = 0
min_prod = min(0, 24*0, -4*0) = 0
result = max(24, 0) = 24

Why: Zero resets product, start fresh

Step 6: Process 5: multiply max_prod and min_prod by 5

max_prod = max(5, 0*5, 0*5) = 5
min_prod = min(5, 0*5, 0*5) = 0
result = max(24, 5) = 24

Why: 5 can start new subarray

Result:

Maximum product subarray is 24

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxProductSubarray(const vector<int>& nums) {
    if (nums.empty()) return 0;
    int max_prod = nums[0];
    int min_prod = nums[0];
    int result = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
        int curr = nums[i];
        if (curr < 0) {
            swap(max_prod, min_prod); // negative flips max and min
        }
        max_prod = max(curr, max_prod * curr); // max product ending here
        min_prod = min(curr, min_prod * curr); // min product ending here
        result = max(result, max_prod); // update global max
    }
    return result;
}

int main() {
    vector<int> nums = {2, -3, 4, -1, 0, 5};
    cout << maxProductSubarray(nums) << endl;
    return 0;
}

if (curr < 0) { swap(max_prod, min_prod); // negative flips max and min }

swap max and min when current number is negative to handle sign flip

max_prod = max(curr, max_prod * curr); // max product ending here

update max product ending at current position

min_prod = min(curr, min_prod * curr); // min product ending here

update min product ending at current position

result = max(result, max_prod); // update global max

keep track of overall maximum product found

Output

24

Complexity Analysis

Time: O(n) because we scan the array once, updating max and min products at each step

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Compared to checking all subarrays (O(n^2)), this approach is much faster and uses constant space

Edge Cases

empty array

returns 0 as no subarray exists

DSA C++

if (nums.empty()) return 0;

array with one element

returns that element as max product

DSA C++

int max_prod = nums[0];

array with zeros

resets product calculation at zero, starts fresh after zero

DSA C++

max_prod = max(curr, max_prod * curr);

array with all negative numbers

correctly swaps max and min to find max product

DSA C++

if (curr < 0) { swap(max_prod, min_prod); }

When to Use This Pattern

When asked for the maximum product of a continuous subarray, track both max and min products because negative numbers can flip signs and affect the result.

Common Mistakes

Mistake: Not tracking the minimum product, so negative numbers cause wrong results
Fix: Track both max and min products and swap them when current number is negative

Mistake: Resetting max product incorrectly on zero without considering min product
Fix: Use max(curr, max_prod * curr) to handle zero and start fresh properly

Summary

Finds the largest product of any continuous subarray in a list.

Use when you need the maximum product of a subarray, especially with negative numbers involved.

Keep track of both maximum and minimum products at each step because negatives flip signs.

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