Maximum Product Subarray

medium
Dynamic ProgrammingArrayDynamic Programming

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product and return the product. A subarray is a contiguous subsequence of the array.

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

Examples

Example 1

  • Input: nums = [2,3,-2,4]
  • Output: 6
  • Explanation: The subarray [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 contiguous subarray.

Example 3

  • Input: nums = [-2,3,-4]
  • Output: 24
  • Explanation: The entire array [-2,3,-4] has the product 24.

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Brute Force

Intuition

Check every possible contiguous subarray by using two nested loops. For each starting index, extend the subarray one element at a time while maintaining the running product. Track the maximum product seen across all subarrays. This approach is straightforward but becomes slow for large inputs.

Algorithm

  1. Initialize maxProd to the smallest possible integer value.
  2. For each starting index i, initialize a running product to 1.
  3. For each ending index j from i to n-1, multiply the running product by nums[j].
  4. Update maxProd if the running product is larger.
  5. Return maxProd.
TimeO(n^2)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxProd = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            int product = 1;
            for (int j = i; j < nums.size(); j++) {
                product *= nums[j];
                maxProd = max(maxProd, product);
            }
        }
        return maxProd;
    }
};
Java 21
class Solution {
    public int maxProduct(int[] nums) {
        int maxProd = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int product = 1;
            for (int j = i; j < nums.length; j++) {
                product *= nums[j];
                maxProd = Math.max(maxProd, product);
            }
        }
        return maxProd;
    }
}
Python 3.12
def maxProduct(nums: list[int]) -> int:
    max_prod = float('-inf')
    for i in range(len(nums)):
        product = 1
        for j in range(i, len(nums)):
            product *= nums[j]
            max_prod = max(max_prod, product)
    return max_prod
Go 1.26
func maxProduct(nums []int) int {
    maxProd := nums[0]
    for i := 0; i < len(nums); i++ {
        product := 1
        for j := i; j < len(nums); j++ {
            product *= nums[j]
            if product > maxProd {
                maxProd = product
            }
        }
    }
    return maxProd
}
Approach 2

Track Min and Max

Intuition

The key challenge with products is that a negative number can flip the sign: a very small negative product can become the largest positive product when multiplied by another negative number. To handle this, we track both the current maximum product and the current minimum product ending at each position. At each step, we consider three candidates: the current element alone, the current element times the previous max, and the current element times the previous min. We update the global result with the running maximum.

Algorithm

  1. Initialize currentMax, currentMin, and result all to the first element.
  2. Iterate from the second element to the end.
  3. If the current element is negative, swap currentMax and currentMin (because multiplying by a negative flips the ordering).
  4. Set currentMax to the maximum of nums[i] and currentMax * nums[i].
  5. Set currentMin to the minimum of nums[i] and currentMin * nums[i].
  6. Update result to the maximum of result and currentMax.
  7. Return result.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int currentMax = nums[0];
        int currentMin = nums[0];
        int result = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < 0) {
                swap(currentMax, currentMin);
            }
            currentMax = max(nums[i], currentMax * nums[i]);
            currentMin = min(nums[i], currentMin * nums[i]);
            result = max(result, currentMax);
        }

        return result;
    }
};
Java 21
class Solution {
    public int maxProduct(int[] nums) {
        int currentMax = nums[0];
        int currentMin = nums[0];
        int result = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = currentMax;
                currentMax = currentMin;
                currentMin = temp;
            }
            currentMax = Math.max(nums[i], currentMax * nums[i]);
            currentMin = Math.min(nums[i], currentMin * nums[i]);
            result = Math.max(result, currentMax);
        }

        return result;
    }
}
Python 3.12
def maxProduct(nums: list[int]) -> int:
    current_max = nums[0]
    current_min = nums[0]
    result = nums[0]

    for i in range(1, len(nums)):
        if nums[i] < 0:
            current_max, current_min = current_min, current_max

        current_max = max(nums[i], current_max * nums[i])
        current_min = min(nums[i], current_min * nums[i])
        result = max(result, current_max)

    return result
Go 1.26
func maxProduct(nums []int) int {
    currentMax := nums[0]
    currentMin := nums[0]
    result := nums[0]

    for i := 1; i < len(nums); i++ {
        if nums[i] < 0 {
            currentMax, currentMin = currentMin, currentMax
        }
        if nums[i] > currentMax*nums[i] {
            currentMax = nums[i]
        } else {
            currentMax = currentMax * nums[i]
        }
        if nums[i] < currentMin*nums[i] {
            currentMin = nums[i]
        } else {
            currentMin = currentMin * nums[i]
        }
        if currentMax > result {
            result = currentMax
        }
    }

    return result
}

Frequently asked questions

What is the optimal time complexity of Maximum Product Subarray?

The most efficient approach in this guide ("Track Min and Max") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Maximum Product Subarray use?

Maximum Product Subarray is a medium-level Dynamic Programming problem involving Array, Dynamic Programming. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Maximum Product Subarray be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Maximum Subarray

Original problem: leetcode.com

Loading editor...
Input
nums=
[2,3,-2,4]
Expected Output
6