Maximum Product Subarray in DSA C

Mental Model

We want to find the largest product of a continuous part of the array. Because multiplying negatives can flip 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 (maximum product), you remember both your farthest forward and backward steps because a backward step might help you jump forward later.

Array: [2] -> [-3] -> [4] -> [-1] -> [0] -> [5]
Tracking max_prod and min_prod at each step

Dry Run Walkthrough

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

Goal: Find the maximum product of any continuous subarray

Step 1: Start with first element: max_prod = 2, min_prod = 2, result = 2

max_prod=2, min_prod=2, result=2

Why: Initialize tracking with first element to start comparisons

Step 2: Process -3: swap max_prod and min_prod because -3 is negative; max_prod = max(-3, 2 * -3) = -3; min_prod = min(-3, 2 * -3) = -6; result = max(2, -3) = 2

max_prod=-3, min_prod=-6, result=2

Why: Negative flips max and min, so swap to track correct values

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

max_prod=4, min_prod=-24, result=4

Why: Positive number updates max and min normally

Step 4: Process -1: swap max_prod and min_prod; max_prod = max(-1, -24 * -1) = 24; min_prod = min(-1, 4 * -1) = -4; result = max(4, 24) = 24

max_prod=24, min_prod=-4, result=24

Why: Negative flips max and min again, potentially increasing max product

Step 5: Process 0: max_prod = max(0, 24 * 0) = 0; min_prod = min(0, -4 * 0) = 0; result = max(24, 0) = 24

max_prod=0, min_prod=0, result=24

Why: Zero resets product tracking

Step 6: Process 5: max_prod = max(5, 0 * 5) = 5; min_prod = min(5, 0 * 5) = 0; result = max(24, 5) = 24

max_prod=5, min_prod=0, result=24

Why: Positive number updates max product, but result remains max so far

Result:

Maximum product subarray = 24

Annotated Code

DSA C

#include <stdio.h>

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

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

int maxProduct(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    int max_prod = nums[0];
    int min_prod = nums[0];
    int result = nums[0];

    for (int i = 1; i < numsSize; i++) {
        if (nums[i] < 0) {
            int temp = max_prod;
            max_prod = min_prod;
            min_prod = temp;
        }
        max_prod = max(nums[i], max_prod * nums[i]);
        min_prod = min(nums[i], min_prod * nums[i]);
        if (max_prod > result) {
            result = max_prod;
        }
    }
    return result;
}

int main() {
    int nums[] = {2, -3, 4, -1, 0, 5};
    int size = sizeof(nums) / sizeof(nums[0]);
    int max_product = maxProduct(nums, size);
    printf("Maximum product subarray = %d\n", max_product);
    return 0;
}

if (nums[i] < 0) { int temp = max_prod; max_prod = min_prod; min_prod = temp; }

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

max_prod = max(nums[i], max_prod * nums[i]);

update max product ending at current index

min_prod = min(nums[i], min_prod * nums[i]);

update min product ending at current index

if (max_prod > result) { result = max_prod; }

update overall maximum product found so far

Output

Maximum product subarray = 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 to track products, no extra arrays

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 (numsSize == 0) return 0;

array with one element

returns that element as max product

DSA C

int max_prod = nums[0]; int min_prod = nums[0]; int result = nums[0];

array with zeros

resets product tracking to zero, allowing new subarray start

DSA C

max_prod = max(nums[i], max_prod * nums[i]); min_prod = min(nums[i], min_prod * nums[i]);

When to Use This Pattern

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

Common Mistakes

Mistake: Not swapping max and min products when encountering a negative number
Fix: Swap max and min before updating them when current number is negative

Mistake: Only tracking max product and ignoring min product
Fix: Track both max and min products to handle negative numbers correctly

Summary

Finds the maximum product of any continuous subarray in an array.

Use when you need the largest product from a sequence of numbers that can include negatives and zeros.

Keep track of both maximum and minimum products at each step because negatives can flip the sign and change the maximum.