152. Maximum Product Subarray Solution

Q: Is Maximum Product Subarray easy or hard?

Maximum Product Subarray is considered a medium difficulty problem. The challenge comes from handling negative numbers and zeros correctly, which requires tracking both maximum and minimum products instead of only a running maximum.

Q: How to solve Maximum Product Subarray in O(n)?

Iterate through the array while keeping two values: the maximum product and minimum product ending at the current index. For each element, compute the new candidates using the current number, number × previous max, and number × previous min. Update the global maximum after each step. This single pass produces the result in O(n) time.

Q: What is the best approach for Maximum Product Subarray?

The most efficient approach uses dynamic programming with two variables that track the maximum and minimum product ending at each index. This handles negative numbers because a negative value can turn a small minimum product into a large maximum. The algorithm runs in O(n) time and O(1) space.

Q: What data structure is used in Maximum Product Subarray?

The problem primarily uses arrays and dynamic programming concepts. Instead of storing a full DP table, the optimized solution keeps only two variables representing the current maximum and minimum products, reducing memory usage to constant space.

Q: What is the time complexity of Maximum Product Subarray?

The optimal solutions run in O(n) time because the array is scanned once while updating running products. Both the dynamic programming method and the prefix–suffix tracking approach maintain constant additional variables, giving O(1) space complexity.

Q: Maximum Product Subarray Python or Java solution approach?

In Python or Java, maintain two variables for the current maximum and minimum product and iterate through the array once. At each step compute new candidates using multiplication with the current element, then update the result. This implementation runs in O(n) time and O(1) space.

Q: Is Maximum Product Subarray asked at Google, Amazon, or Meta?

Maximum Product Subarray is a common medium-level interview problem that has appeared in coding interviews at companies like Amazon, Google, and Meta. It tests understanding of dynamic programming, handling negative numbers, and reasoning about subarray products.

The problem

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

1 <= nums.length <= 2 * 10⁴
-10 <= nums[i] <= 10
The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

Approach overview

Problem Overview: Given an integer array, find the contiguous subarray that has the largest product and return that product. Negative numbers make this problem tricky because multiplying two negatives can suddenly produce a large positive value.

Approach 1: Dynamic Programming with Two Variables (O(n) time, O(1) space)

This approach tracks two values while scanning the array: the maximum product ending at the current index and the minimum product ending at the current index. The minimum is necessary because a negative number can flip a small negative product into a large positive one. For every element num, compute three candidates: num, num * currentMax, and num * currentMin. Update the running maximum and minimum accordingly. Maintain a global result that stores the best product seen so far.

The key insight is that the optimal subarray ending at position i depends only on the previous step. This makes the algorithm a compact form of dynamic programming with constant memory. You iterate once through the array, updating two variables and the result. Time complexity is O(n) and space complexity is O(1), making it the standard optimal solution used in interviews.

Approach 2: Prefix and Suffix Product Tracking (O(n) time, O(1) space)

This method scans the array twice conceptually by tracking cumulative products from both directions. Compute a running prefix product from left to right and a suffix product from right to left. If a zero appears, reset the running product because any subarray crossing that zero becomes zero. The maximum product subarray must appear either in a prefix segment or a suffix segment when negatives are balanced.

During the traversal, update the result with the maximum of the prefix product, suffix product, and current best. This technique works because reversing the traversal effectively handles cases where an odd number of negative values causes the optimal product to appear after dropping the first negative element. The algorithm still runs in O(n) time with O(1) space and uses simple multiplication without maintaining two states.

Recommended for interviews: The dynamic programming approach with two variables is the solution most interviewers expect. It shows you understand how negative numbers affect products and how to maintain both maximum and minimum states. The prefix–suffix approach is also efficient but less commonly discussed during interviews. Demonstrating the brute reasoning about negatives first and then implementing the DP solution signals strong understanding of dynamic programming patterns on arrays.

Approach 1: Dynamic Programming with Two Variables

This approach maintains two variables for each element in the array: the maximum product up to that element and the minimum product up to that element. We update these variables as we iterate through the array. This accommodates both the product of consecutive elements and the inversion effect caused by negative numbers.

Python

def maxProduct(nums):
    maxProduct = nums[0]
    currMax = nums[0]
    currMin = nums[0]
    for i in range(1, len(nums)):
        if nums[i] < 0:
            currMax, currMin = currMin, currMax
        currMax = max(nums[i], nums[i] * currMax)
        currMin = min(nums[i], nums[i] * currMin)
        maxProduct = max(maxProduct, currMax)
    return maxProduct

print(maxProduct([2, 3, -2, 4]))

Java

public class MaxProductSubarray {
    public static int maxProduct(int[] nums) {
        int maxProduct = nums[0];
        int currMax = nums[0];
        int currMin = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = currMax;
                currMax = currMin;
                currMin = temp;
            }
            currMax = Math.max(nums[i], nums[i] * currMax);
            currMin = Math.min(nums[i], nums[i] * currMin);
            maxProduct = Math.max(maxProduct, currMax);
        }
        return maxProduct;
    }
    public static void main(String[] args) {
        int[] nums = {2, 3, -2, 4};
        System.out.println(maxProduct(nums));
    }
}

C++

#include <vector>
#include <iostream>

int maxProduct(std::vector<int>& nums) {
    int maxProduct = nums[0];
    int currMax = nums[0];
    int currMin = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] < 0) std::swap(currMax, currMin);
        currMax = std::max(nums[i], nums[i] * currMax);
        currMin = std::min(nums[i], nums[i] * currMin);
        maxProduct = std::max(maxProduct, currMax);
    }
    return maxProduct;
}

int main() {
    std::vector<int> nums = {2, 3, -2, 4};
    std::cout << maxProduct(nums) << std::endl;
    return 0;
}

JavaScript

function maxProduct(nums) {
    let maxProduct = nums[0];
    let currMax = nums[0];
    let currMin = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < 0) {
            let temp = currMax;
            currMax = currMin;
            currMin = temp;
        }
        currMax = Math.max(nums[i], nums[i] * currMax);
        currMin = Math.min(nums[i], nums[i] * currMin);
        maxProduct = Math.max(maxProduct, currMax);
    }
    return maxProduct;
}

console.log(maxProduct([2, 3, -2, 4]));

#include <stdio.h>

int maxProduct(int* nums, int numsSize) {
    int maxProduct = nums[0];
    int currMax = nums[0];
    int currMin = nums[0];
    for(int i = 1; i < numsSize; i++) {
        if (nums[i] < 0) {
            int temp = currMax;
            currMax = currMin;
            currMin = temp;
        }
        currMax = nums[i] > nums[i] * currMax ? nums[i] : nums[i] * currMax;
        currMin = nums[i] < nums[i] * currMin ? nums[i] : nums[i] * currMin;
        maxProduct = currMax > maxProduct ? currMax : maxProduct;
    }
    return maxProduct;
}

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

using System;

public class MaxProductSubarray {
    public static int MaxProduct(int[] nums) {
        int maxProduct = nums[0];
        int currMax = nums[0];
        int currMin = nums[0];
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] < 0) {
                int temp = currMax;
                currMax = currMin;
                currMin = temp;
            }
            currMax = Math.Max(nums[i], nums[i] * currMax);
            currMin = Math.Min(nums[i], nums[i] * currMin);
            maxProduct = Math.Max(maxProduct, currMax);
        }
        return maxProduct;
    }
    public static void Main() {
        int[] nums = {2, 3, -2, 4};
        Console.WriteLine(MaxProduct(nums));
    }
}

Python's tuple unpacking makes swapping currMax and currMin straightforward when encountering negative numbers. The solution details remain the same.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Prefix and Suffix Product Tracking

In this approach, we calculate the prefix product and suffix product for each element of the array, capturing the highest product subarray that may begin or end with an array boundary. We track the maximum of the prefix or suffix products.

Python

def maxProduct(nums):
    n = len(nums)
    maxProduct = nums[0]
    prefixProduct = 1
    suffixProduct = 1
    for i in range(n):
        prefixProduct = 1 if prefixProduct == 0 else prefixProduct * nums[i]
        suffixProduct = 1 if suffixProduct == 0 else suffixProduct * nums[n - 1 - i]
        maxProduct = max(maxProduct, prefixProduct, suffixProduct)
    return maxProduct

print(maxProduct([2, 3, -2, 4]))

Java

public class MaxProductSubarray {
    public static int maxProduct(int[] nums) {
        int maxProduct = nums[0];
        int prefixProduct = 1;
        int suffixProduct = 1;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            prefixProduct = prefixProduct == 0 ? nums[i] : prefixProduct * nums[i];
            suffixProduct = suffixProduct == 0 ? nums[n - 1 - i] : suffixProduct * nums[n - 1 - i];
            maxProduct = Math.max(maxProduct, Math.max(prefixProduct, suffixProduct));
        }
        return maxProduct;
    }
    public static void main(String[] args) {
        int[] nums = {2, 3, -2, 4};
        System.out.println(maxProduct(nums));
    }
}

C++

#include <vector>
#include <iostream>

int maxProduct(std::vector<int>& nums) {
    int maxProduct = nums[0];
    int prefixProduct = 1;
    int suffixProduct = 1;
    for (int i = 0; i < nums.size(); i++) {
        prefixProduct = prefixProduct == 0 ? nums[i] : prefixProduct * nums[i];
        suffixProduct = suffixProduct == 0 ? nums[nums.size() - 1 - i] : suffixProduct * nums[nums.size() - 1 - i];
        maxProduct = std::max(maxProduct, std::max(prefixProduct, suffixProduct));
    }
    return maxProduct;
}

int main() {
    std::vector<int> nums = {2, 3, -2, 4};
    std::cout << maxProduct(nums) << std::endl;
    return 0;
}

JavaScript

function maxProduct(nums) {
    let maxProduct = nums[0];
    let prefixProduct = 1;
    let suffixProduct = 1;
    let n = nums.length;
    for (let i = 0; i < n; i++) {
        prefixProduct = prefixProduct === 0 ? nums[i] : prefixProduct * nums[i];
        suffixProduct = suffixProduct === 0 ? nums[n - 1 - i] : suffixProduct * nums[n - 1 - i];
        maxProduct = Math.max(maxProduct, prefixProduct, suffixProduct);
    }
    return maxProduct;
}

console.log(maxProduct([2, 3, -2, 4]));

#include <stdio.h>

int maxProduct(int* nums, int numsSize) {
    int maxProduct = nums[0];
    int prefixProduct = 1;
    int suffixProduct = 1;
    for (int i = 0; i < numsSize; i++) {
        prefixProduct = prefixProduct == 0 ? nums[i] : prefixProduct * nums[i];
        suffixProduct = suffixProduct == 0 ? nums[numsSize - 1 - i] : suffixProduct * nums[numsSize - 1 - i];
        maxProduct = prefixProduct > maxProduct ? prefixProduct : maxProduct;
        maxProduct = suffixProduct > maxProduct ? suffixProduct : maxProduct;
    }
    return maxProduct;
}

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

using System;

public class MaxProductSubarray {
    public static int MaxProduct(int[] nums) {
        int maxProduct = nums[0];
        int prefixProduct = 1;
        int suffixProduct = 1;
        for (int i = 0; i < nums.Length; i++) {
            prefixProduct = prefixProduct == 0 ? nums[i] : prefixProduct * nums[i];
            suffixProduct = suffixProduct == 0 ? nums[nums.Length - 1 - i] : suffixProduct * nums[nums.Length - 1 - i];
            maxProduct = Math.Max(maxProduct, Math.Max(prefixProduct, suffixProduct));
        }
        return maxProduct;
    }
    public static void Main() {
        int[] nums = {2, 3, -2, 4};
        Console.WriteLine(MaxProduct(nums));
    }
}

Python calculates prefix and suffix products within a single traversal over the array with tuple unpacking for swaps. Updates to maxProduct are done by comparing the accumulated products.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function maxProduct(nums: number[]): number {
    let [f, g, ans] = [nums[0], nums[0], nums[0]];
    for (let i = 1; i < nums.length; ++i) {
        const [ff, gg] = [f, g];
        f = Math.max(nums[i], ff * nums[i], gg * nums[i]);
        g = Math.min(nums[i], ff * nums[i], gg * nums[i]);
        ans = Math.max(ans, f);
    }
    return ans;
}

func maxProduct(nums []int) int {
	f, g, ans := nums[0], nums[0], nums[0]
	for _, x := range nums[1:] {
		ff, gg := f, g
		f = max(x, max(ff*x, gg*x))
		g = min(x, min(ff*x, gg*x))
		ans = max(ans, f)
	}
	return ans
}

Rust

impl Solution {
    pub fn max_product(nums: Vec<i32>) -> i32 {
        let mut f = nums[0];
        let mut g = nums[0];
        let mut ans = nums[0];
        for &x in nums.iter().skip(1) {
            let (ff, gg) = (f, g);
            f = x.max(x * ff).max(x * gg);
            g = x.min(x * ff).min(x * gg);
            ans = ans.max(f);
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with Two Variables	Time Complexity: O(n) Space Complexity: O(1)
Prefix and Suffix Product Tracking	Time Complexity: O(n) Space Complexity: O(1)
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming with Two Variables	O(n)	O(1)	Best general solution; handles negative numbers efficiently and is the most common interview answer.
Prefix and Suffix Product Tracking	O(n)	O(1)	Useful alternative when reasoning about products from both directions or handling segments separated by zeros.

Frequently asked questions

Is Maximum Product Subarray easy or hard?

Maximum Product Subarray is considered a medium difficulty problem. The challenge comes from handling negative numbers and zeros correctly, which requires tracking both maximum and minimum products instead of only a running maximum.

How to solve Maximum Product Subarray in O(n)?

Iterate through the array while keeping two values: the maximum product and minimum product ending at the current index. For each element, compute the new candidates using the current number, number × previous max, and number × previous min. Update the global maximum after each step. This single pass produces the result in O(n) time.

What is the best approach for Maximum Product Subarray?

The most efficient approach uses dynamic programming with two variables that track the maximum and minimum product ending at each index. This handles negative numbers because a negative value can turn a small minimum product into a large maximum. The algorithm runs in O(n) time and O(1) space.

What data structure is used in Maximum Product Subarray?

The problem primarily uses arrays and dynamic programming concepts. Instead of storing a full DP table, the optimized solution keeps only two variables representing the current maximum and minimum products, reducing memory usage to constant space.

What is the time complexity of Maximum Product Subarray?

The optimal solutions run in O(n) time because the array is scanned once while updating running products. Both the dynamic programming method and the prefix–suffix tracking approach maintain constant additional variables, giving O(1) space complexity.

Maximum Product Subarray Python or Java solution approach?

In Python or Java, maintain two variables for the current maximum and minimum product and iterate through the array once. At each step compute new candidates using multiplication with the current element, then update the result. This implementation runs in O(n) time and O(1) space.

Is Maximum Product Subarray asked at Google, Amazon, or Meta?

Maximum Product Subarray is a common medium-level interview problem that has appeared in coding interviews at companies like Amazon, Google, and Meta. It tests understanding of dynamic programming, handling negative numbers, and reasoning about subarray products.

Maximum Product Subarray solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Two Variables

Approach 2: Prefix and Suffix Product Tracking

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Product Subarray solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Two Variables

Approach 2: Prefix and Suffix Product Tracking

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems