Maximum Product Subarray in DSA C++ - Build from Scratch

Maximum Product Subarray

📖 Scenario: Imagine you are analyzing daily stock price changes represented as a list of integers. Some days the price goes up (positive numbers), some days it goes down (negative numbers), and some days it stays the same (zero). You want to find the period where the product of these daily changes is the highest.

🎯 Goal: Build a program that finds the maximum product of a contiguous subarray within the given list of daily changes.

📋 What You'll Learn

Create a vector of integers called nums with the exact values: {2, 3, -2, 4}

Create two integer variables called max_product and min_product initialized to the first element of nums

Use a for loop with variable i starting from 1 to iterate over nums

Inside the loop, update max_product and min_product considering the current number and previous products

Create an integer variable called result initialized to the first element of nums

Update result inside the loop to keep track of the maximum product found so far

Print the value of result at the end

💡 Why This Matters

🌍 Real World

This technique helps in financial analysis to find the best period for stock price growth or loss by analyzing daily changes.

💼 Career

Understanding maximum product subarray is useful in software engineering roles involving algorithm optimization, data analysis, and problem solving.

1

Create the data vector

Create a std::vector<int> called nums with these exact values: {2, 3, -2, 4}

DSA C++

# Your code here

Hint

Use std::vector<int> nums = {2, 3, -2, 4}; to create the vector.

2

Initialize variables for tracking products

Create two integer variables called max_product and min_product and initialize both to nums[0]. Also create an integer variable called result and initialize it to nums[0].

DSA C++

#include 
#include 

int main() {
    std::vector nums = {2, 3, -2, 4};

    // Initialize max_product, min_product, and result
    # Your code here

    return 0;
}

Hint

Initialize all three variables to the first element of nums.

3

Implement the main loop to find maximum product

Use a for loop with variable i starting from 1 to iterate over nums. Inside the loop, create a temporary variable temp_max to store the current max_product. Update max_product to the maximum of nums[i], max_product * nums[i], and min_product * nums[i]. Update min_product to the minimum of nums[i], temp_max * nums[i], and min_product * nums[i]. Update result to the maximum of result and max_product.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector nums = {2, 3, -2, 4};

    int max_product = nums[0];
    int min_product = nums[0];
    int result = nums[0];

    // Loop through nums starting from index 1
    # Your code here

    return 0;
}

Hint

Remember to include #include <algorithm> for std::max and std::min. Use a temporary variable to hold the old max_product before updating.

4

Print the maximum product result

Print the value of result using std::cout.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector nums = {2, 3, -2, 4};

    int max_product = nums[0];
    int min_product = nums[0];
    int result = nums[0];

    for (int i = 1; i < nums.size(); i++) {
        int temp_max = max_product;
        max_product = std::max({nums[i], max_product * nums[i], min_product * nums[i]});
        min_product = std::min({nums[i], temp_max * nums[i], min_product * nums[i]});
        result = std::max(result, max_product);
    }

    // Print the result
    # Your code here

    return 0;
}

Hint

Use std::cout << result << std::endl; to print the maximum product.

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