Find Maximum Product Subarray Dynamic Programming - Optimal Approach

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

Visualization Player

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❯

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

Code

C++

Python

Java

Rust

Kotlin

Swift

#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❯

Case	Time Complexity	Explanation
Best Case	O(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 Case	O(n)	The algorithm always traverses the entire array once to keep track of current maximum and minimum products due to possible negative values.
Worst Case	O(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.

⬅ Previous TopicFind Length of Largest Subarray with 0 Sum

Next Topic ⮕Binary Search in Array using Iteration

Comments

Loading comments...