Maximum Product Subarray in DSA C - Build from Scratch

Maximum Product Subarray

📖 Scenario: You are working on a financial analysis tool that needs to find the maximum product of a contiguous subarray within a list of daily stock returns. This helps identify the period with the highest compounded return.

🎯 Goal: Build a program that finds the maximum product of any contiguous subarray in a given array of integers.

📋 What You'll Learn

Create an integer array called nums with the exact values: {2, 3, -2, 4}

Create an integer variable called n that stores the length of nums

Create integer variables maxProd, minProd, and result to track the maximum product, minimum product, and final result respectively

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

Inside the loop, update maxProd and minProd by considering nums[i], maxProd * nums[i], and minProd * nums[i]

Update result to be the maximum of itself and maxProd

Print the value of result at the end

💡 Why This Matters

🌍 Real World

Finding maximum product subarrays helps in financial analysis to identify periods of highest compounded returns or in signal processing to find segments with maximum gain.

💼 Career

This problem is common in technical interviews and helps develop skills in array manipulation, dynamic programming, and handling edge cases with negative numbers.

1

Create the input array

Create an integer array called nums with the exact values {2, 3, -2, 4} and an integer variable n that stores the length of nums.

DSA C

# Create the array nums and variable n
// Your code here

Hint

Use int nums[] = {2, 3, -2, 4}; to create the array and int n = sizeof(nums) / sizeof(nums[0]); to get its length.

2

Initialize tracking variables

Create integer variables maxProd, minProd, and result. Initialize all three to the first element of nums.

DSA C

#include 

int main() {
    int nums[] = {2, 3, -2, 4};
    int n = sizeof(nums) / sizeof(nums[0]);

    // Initialize maxProd, minProd, and result to nums[0]
    // Your code here

    return 0;
}

Hint

Set maxProd, minProd, and result equal to nums[0].

3

Implement the main loop to find maximum product

Use a for loop with variable i from 1 to n - 1 to iterate over nums. Inside the loop, create an integer tempMax to store the current maxProd. Update maxProd to the maximum of nums[i], maxProd * nums[i], and minProd * nums[i]. Update minProd to the minimum of nums[i], tempMax * nums[i], and minProd * nums[i]. Then update result to the maximum of result and maxProd. Use the helper functions max and min defined below.

DSA C

#include 

int max(int a, int b) {
    return (a > b) ? a : b;
}

int min(int a, int b) {
    return (a < b) ? a : b;
}

int main() {
    int nums[] = {2, 3, -2, 4};
    int n = sizeof(nums) / sizeof(nums[0]);

    int maxProd = nums[0];
    int minProd = nums[0];
    int result = nums[0];

    // Use a for loop from i = 1 to n - 1
    // Inside the loop, update maxProd, minProd, and result
    // Your code here

    return 0;
}

Hint

Remember to save the old maxProd in tempMax before updating. Use helper functions max3 and min3 to find max and min of three values.

4

Print the maximum product result

Print the value of result using printf.

DSA C

#include 

int max(int a, int b) {
    return (a > b) ? a : b;
}

int min(int a, int b) {
    return (a  result) {
            result = maxProd;
        }
    }

    // Print the result
    // Your code here

    return 0;
}

Hint

Use printf("%d\n", result); to print the maximum product.

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