Find Maximum Product Subarray - Dynamic Programming - Visualization

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given an array of integers (which may contain positive numbers, negative numbers, and zeros), your task is to find the maximum product that can be obtained from a contiguous subarray.

  • You can choose any contiguous part of the array (including a single element).
  • The subarray must have at least one element.

If the array is empty, the answer should be 0.

Examples❯

Input Array Maximum Product Description
[2, 3, -2, 4] 6 Subarray [2, 3] gives the max product 6
[-2, 0, -1] 0 Zero breaks product chains, so max product is 0
[-2, 3, -4] 24 Subarray [3, -4] gives 3 * -4 = -12, but [-2, 3, -4] gives 24
[0, 0, 0] 0 All elements are zero, so product is 0
[5] 5 Single element positive, product is the element itself
[-5] -5 Single negative number, product is the element itself
[1, -2, -3, 4] 24 Subarray [-2, -3, 4] gives max product
[6, -3, -10, 0, 2] 180 Subarray [6, -3, -10] gives 180
[] 0 Empty array has no elements; product is 0

Solution❯

Understanding the Problem

We are given an array of integers. Our goal is to find the maximum product subarray — that is, the contiguous subarray that gives the largest product when its elements are multiplied together.

Unlike sum problems, multiplication has unique challenges:

  • Multiplying two negative numbers gives a positive number.
  • Multiplying any number with zero resets the product to zero.
  • Negative numbers can reduce the product or, if paired well, create the maximum one.

Step-by-Step Solution Using Example

Example: nums = [2, 3, -2, 4]

We go through the array one element at a time. At each step, we keep track of:

  • maxProductEndingHere: The maximum product that ends at the current index.
  • minProductEndingHere: The minimum product that ends at the current index.

This is important because a negative number might make a small (even negative) product become a large positive one when multiplied.

Step-by-step execution:

  • Start with max = min = result = 2 (first number)
  • Next, 3:
    • tempMax = max(3, 2*3, 2*3) = 6
    • tempMin = min(3, 2*3, 2*3) = 3
    • Update result = max(6, 2) = 6
  • Next, -2:
    • tempMax = max(-2, 6*(-2), 3*(-2)) = max(-2, -12, -6) = -2
    • tempMin = min(-2, 6*(-2), 3*(-2)) = min(-2, -12, -6) = -12
    • Swap min and max because of negative
    • Update result = max(6, -2) = 6
  • Next, 4:
    • tempMax = max(4, -2*4, -12*4) = max(4, -8, -48) = 4
    • tempMin = min(4, -2*4, -12*4) = min(4, -8, -48) = -48
    • Update result = max(6, 4) = 6

Final Answer = 6

Edge Case Handling

What happens in special cases?

  • Array contains 0: Restart max and min at 0; product splits.
  • All positive: Product of full array is maximum.
  • All negative (even count): Product of entire array is maximum (negatives cancel).
  • All negative (odd count): Drop one negative (either from start or end) to get maximum product.
  • Single element: That is the result.
  • Empty array: No subarray exists. Return 0.

Key Intuition for Beginners

  • We are not just tracking the max product — we also track the min because it can become max after a negative.
  • Think of zero as a wall. You can’t continue the product across it.
  • Swapping min and max when we see a negative is a key trick.

Finally

This is a classic dynamic programming problem. At each step, you use previous results to decide your current best. You only need one pass through the array, so the time complexity is O(n).

By managing both the maximum and minimum product ending at each position, we can smartly deal with negatives and zeros to find the optimal subarray product.

Algorithm Steps❯

  1. Given an array arr of integers.
  2. Initialize three variables: max_product = arr[0], min_product = arr[0], and result = arr[0].
  3. Traverse the array from index 1:
  4. → If the current element is negative, swap max_product and min_product.
  5. → Update max_product as the maximum of current element and current element * max_product.
  6. → Update min_product as the minimum of current element and current element * min_product.
  7. → Update result as the maximum of result and max_product.
  8. Return result as the final maximum product subarray.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int maxProductSubarray(int arr[], int n) {
    int maxProduct = arr[0], minProduct = arr[0], result = arr[0];

    for (int i = 1; i < n; i++) {
        int num = arr[i];
        if (num < 0) {
            int temp = maxProduct;
            maxProduct = minProduct;
            minProduct = temp;
        }

        maxProduct = (num > num * maxProduct) ? num : num * maxProduct;
        minProduct = (num < num * minProduct) ? num : num * minProduct;

        result = (result > maxProduct) ? result : maxProduct;
    }

    return result;
}

int main() {
    int arr[] = {2, 3, -2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Maximum Product Subarray: %d\n", maxProductSubarray(arr, n));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)In the best case, the array contains only positive numbers, and a single pass through the array is sufficient to compute the result.
Average CaseO(n)The algorithm always traverses the entire array once to keep track of current maximum and minimum products due to possible negative values.
Worst CaseO(n)Even if the array has many sign changes and zeros, the algorithm must still iterate over every element to track product variations.

Space Complexity❯

O(1)

Explanation: The solution uses only a constant number of variables (max_product, min_product, result), so the space used does not grow with input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...