Find Maximum Product Subarray

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.

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.

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.

#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;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxProductSubarray(vector<int>& arr) {
    int maxProduct = arr[0], minProduct = arr[0], result = arr[0];

    for (int i = 1; i < arr.size(); i++) {
        int num = arr[i];
        if (num < 0)
            swap(maxProduct, minProduct);

        maxProduct = max(num, num * maxProduct);
        minProduct = min(num, num * minProduct);

        result = max(result, maxProduct);
    }

    return result;
}

int main() {
    vector<int> arr = {2, 3, -2, 4};
    cout << "Maximum Product Subarray: " << maxProductSubarray(arr) << endl;
    return 0;
}

def max_product_subarray(arr):
    max_product = min_product = result = arr[0]

    for num in arr[1:]:
        if num < 0:
            max_product, min_product = min_product, max_product

        max_product = max(num, num * max_product)
        min_product = min(num, num * min_product)

        result = max(result, max_product)

    return result

# Sample Input
arr = [2, 3, -2, 4]
print("Maximum Product Subarray:", max_product_subarray(arr))

public class MaximumProductSubarray {
    public static int maxProduct(int[] arr) {
        int maxProduct = arr[0], minProduct = arr[0], result = arr[0];

        for (int i = 1; i < arr.length; i++) {
            int num = arr[i];
            if (num < 0) {
                int temp = maxProduct;
                maxProduct = minProduct;
                minProduct = temp;
            }
            maxProduct = Math.max(num, num * maxProduct);
            minProduct = Math.min(num, num * minProduct);

            result = Math.max(result, maxProduct);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, -2, 4};
        System.out.println("Maximum Product Subarray: " + maxProduct(arr));
    }
}

function maxProductSubarray(arr) {
    let maxProduct = arr[0];
    let minProduct = arr[0];
    let result = arr[0];

    for (let i = 1; i < arr.length; i++) {
        let num = arr[i];
        if (num < 0) {
            [maxProduct, minProduct] = [minProduct, maxProduct];
        }
        maxProduct = Math.max(num, num * maxProduct);
        minProduct = Math.min(num, num * minProduct);
        result = Math.max(result, maxProduct);
    }

    return result;
}

const arr = [2, 3, -2, 4];
console.log("Maximum Product Subarray:", maxProductSubarray(arr));

package main

import (
    "fmt"
)

func maxProduct(nums []int) int {
    maxProduct := nums[0]
    minProduct := nums[0]
    result := nums[0]

    for i := 1; i < len(nums); i++ {
        num := nums[i]
        if num < 0 {
            maxProduct, minProduct = minProduct, maxProduct
        }
        maxProduct = max(num, num*maxProduct)
        minProduct = min(num, num*minProduct)
        result = max(result, maxProduct)
    }

    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    arr := []int{2, 3, -2, 4}
    fmt.Println("Maximum Product Subarray:", maxProduct(arr))
}

fn max_product_subarray(arr: &[i32]) -> i32 {
    let mut max_product = arr[0];
    let mut min_product = arr[0];
    let mut result = arr[0];

    for &num in &arr[1..] {
        if num < 0 {
            std::mem::swap(&mut max_product, &mut min_product);
        }
        max_product = std::cmp::max(num, num * max_product);
        min_product = std::cmp::min(num, num * min_product);
        result = std::cmp::max(result, max_product);
    }

    result
}

fn main() {
    let arr = [2, 3, -2, 4];
    println!("Maximum Product Subarray: {}", max_product_subarray(&arr));
}

fun maxProductSubarray(arr: IntArray): Int {
    var maxProduct = arr[0]
    var minProduct = arr[0]
    var result = arr[0]

    for (i in 1 until arr.size) {
        val num = arr[i]
        if (num < 0) {
            val temp = maxProduct
            maxProduct = minProduct
            minProduct = temp
        }
        maxProduct = maxOf(num, num * maxProduct)
        minProduct = minOf(num, num * minProduct)
        result = maxOf(result, maxProduct)
    }

    return result
}

fun main() {
    val arr = intArrayOf(2, 3, -2, 4)
    println("Maximum Product Subarray: ${maxProductSubarray(arr)}")
}

func maxProductSubarray(_ arr: [Int]) -> Int {
    var maxProduct = arr[0]
    var minProduct = arr[0]
    var result = arr[0]

    for i in 1..<arr.count {
        let num = arr[i]
        if num < 0 {
            swap(&maxProduct, &minProduct)
        }
        maxProduct = max(num, num * maxProduct)
        minProduct = min(num, num * minProduct)
        result = max(result, maxProduct)
    }
    return result
}

var arr = [2, 3, -2, 4]
print("Maximum Product Subarray: \(maxProductSubarray(arr))")

function maxProductSubarray(arr: number[]): number {
    let maxProduct = arr[0];
    let minProduct = arr[0];
    let result = arr[0];

    for (let i = 1; i < arr.length; i++) {
        let num = arr[i];
        if (num < 0) {
            [maxProduct, minProduct] = [minProduct, maxProduct];
        }
        maxProduct = Math.max(num, num * maxProduct);
        minProduct = Math.min(num, num * minProduct);
        result = Math.max(result, maxProduct);
    }

    return result;
}

const arr: number[] = [2, 3, -2, 4];
console.log("Maximum Product Subarray:", maxProductSubarray(arr));

Time complexity

Space complexity

O(1)

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