Maximum Product Subarray

Problem Statement

Given an integer array nums, pick a non-empty contiguous block of elements (a subarray) whose product is as large as possible, and return that product.

The input is chosen so that the product of every subarray fits in a signed 32-bit integer.

Examples

Example 1:

Input: nums = [3,-1,4,2]
Output: 8
Explanation: -1 is the only negative value, so any subarray that includes it has a negative
product. The best subarray without it is [4,2], with product 8.

Example 2:

Input: nums = [-3,0,-5]
Output: 0
Explanation: Every non-empty subarray is either a single negative number or contains 0,
so the best product is 0 (the subarray [0]).

Example 3:

Input: nums = [-2,5,-3,1]
Output: 30
Explanation: Two negatives cancel out: [-2,5,-3] has product 30, and multiplying by 1 keeps it at 30.

Constraints

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

Approach 1: Brute Force over All Subarrays

Algorithm

Fix a start index i, then extend the subarray one element at a time to the right, keeping a running product. Every extension is a new subarray, so compare its product with the best answer seen so far. Reusing the running product avoids recomputing each subarray from scratch.

1. Set best = nums[0] (a valid single-element subarray).
2. For every start i:
   • Set product = 1.
   • For every end j >= i, multiply product by nums[j] and update best = max(best, product).
3. Return best.

Implementation

Python:

from typing import List


class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        best = nums[0]
        n = len(nums)
        for i in range(n):
            product = 1
            for j in range(i, n):
                product *= nums[j]  # product of nums[i..j]
                best = max(best, product)
        return best

Java:

class Solution {
    public int maxProduct(int[] nums) {
        int best = nums[0];
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = i; j < n; j++) {
                product *= nums[j]; // product of nums[i..j]
                best = Math.max(best, product);
            }
        }
        return best;
    }
}

Go:

func maxProduct(nums []int) int {
    best := nums[0]
    n := len(nums)
    for i := 0; i < n; i++ {
        product := 1
        for j := i; j < n; j++ {
            product *= nums[j] // product of nums[i..j]
            if product > best {
                best = product
            }
        }
    }
    return best
}

JavaScript:

function maxProduct(nums) {
    let best = nums[0];
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        let product = 1;
        for (let j = i; j < n; j++) {
            product *= nums[j]; // product of nums[i..j]
            best = Math.max(best, product);
        }
    }
    return best;
}

C#:

using System;

public class Solution {
    public int MaxProduct(int[] nums) {
        int best = nums[0];
        int n = nums.Length;
        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = i; j < n; j++) {
                product *= nums[j]; // product of nums[i..j]
                best = Math.Max(best, product);
            }
        }
        return best;
    }
}

C++:

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

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int best = nums[0];
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = i; j < n; j++) {
                product *= nums[j]; // product of nums[i..j]
                best = max(best, product);
            }
        }
        return best;
    }
};

Complexity Analysis

• Time: O(n²): there are n(n+1)/2 subarrays and each is handled in O(1) thanks to the running product.
• Space: O(1).

Approach 2: Track Running Max and Min (Optimal)

Algorithm

This is Kadane’s algorithm adapted to products. For sums, the best subarray ending at index i depends only on the best one ending at i - 1. For products that is not enough: a very negative product can become the largest product after multiplying by a negative number. So for each index we track two values:

• curMax: the largest product of a subarray that ends at i
• curMin: the smallest (most negative) product of a subarray that ends at i

A subarray ending at i either starts fresh at nums[i] or extends the best/worst subarray ending at i - 1. When nums[i] is negative, multiplying flips the order, so the old minimum produces the new maximum and vice versa. Swapping curMax and curMin before the update handles that. A zero resets both to 0, and the “start fresh” option lets the next element begin a new subarray.

1. Set curMax = curMin = best = nums[0].
2. For each i from 1 to n - 1, with x = nums[i]:
   • If x < 0, swap curMax and curMin.
   • curMax = max(x, curMax * x)
   • curMin = min(x, curMin * x)
   • best = max(best, curMax)
3. Return best.

Every value that is ever computed (curMax * x, curMin * x) is the product of a real subarray, so the 32-bit guarantee covers all intermediate values.

Implementation

Python:

from typing import List


class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        cur_max = cur_min = best = nums[0]
        for i in range(1, len(nums)):
            x = nums[i]
            if x < 0:
                # A negative factor turns the smallest product into the largest
                cur_max, cur_min = cur_min, cur_max
            cur_max = max(x, cur_max * x)  # start fresh or extend
            cur_min = min(x, cur_min * x)
            best = max(best, cur_max)
        return best

Java:

class Solution {
    public int maxProduct(int[] nums) {
        int curMax = nums[0], curMin = nums[0], best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            if (x < 0) {
                // A negative factor turns the smallest product into the largest
                int tmp = curMax;
                curMax = curMin;
                curMin = tmp;
            }
            curMax = Math.max(x, curMax * x); // start fresh or extend
            curMin = Math.min(x, curMin * x);
            best = Math.max(best, curMax);
        }
        return best;
    }
}

Go:

func maxProduct(nums []int) int {
    curMax, curMin, best := nums[0], nums[0], nums[0]
    for _, x := range nums[1:] {
        if x < 0 {
            // A negative factor turns the smallest product into the largest
            curMax, curMin = curMin, curMax
        }
        curMax = max(x, curMax*x) // start fresh or extend (built-in max, Go 1.21+)
        curMin = min(x, curMin*x)
        best = max(best, curMax)
    }
    return best
}

JavaScript:

function maxProduct(nums) {
    let curMax = nums[0], curMin = nums[0], best = nums[0];
    for (let i = 1; i < nums.length; i++) {
        const x = nums[i];
        if (x < 0) {
            // A negative factor turns the smallest product into the largest
            [curMax, curMin] = [curMin, curMax];
        }
        curMax = Math.max(x, curMax * x); // start fresh or extend
        curMin = Math.min(x, curMin * x);
        best = Math.max(best, curMax);
    }
    return best;
}

C#:

using System;

public class Solution {
    public int MaxProduct(int[] nums) {
        int curMax = nums[0], curMin = nums[0], best = nums[0];
        for (int i = 1; i < nums.Length; i++) {
            int x = nums[i];
            if (x < 0) {
                // A negative factor turns the smallest product into the largest
                (curMax, curMin) = (curMin, curMax);
            }
            curMax = Math.Max(x, curMax * x); // start fresh or extend
            curMin = Math.Min(x, curMin * x);
            best = Math.Max(best, curMax);
        }
        return best;
    }
}

C++:

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

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int curMax = nums[0], curMin = nums[0], best = nums[0];
        for (size_t i = 1; i < nums.size(); i++) {
            int x = nums[i];
            if (x < 0) {
                // A negative factor turns the smallest product into the largest
                swap(curMax, curMin);
            }
            curMax = max(x, curMax * x); // start fresh or extend
            curMin = min(x, curMin * x);
            best = max(best, curMax);
        }
        return best;
    }
};

Complexity Analysis

• Time: O(n): one pass with constant work per element.
• Space: O(1): three variables, regardless of input size.

Key Insights

1. Negatives flip the order. The smallest product ending at i - 1 becomes the largest after multiplying by a negative number, so the minimum is just as important as the maximum.
2. Zero splits the array. A zero forces both running values to 0; the max(x, ...) / min(x, ...) “start fresh” option lets the next element begin a new subarray.
3. Kadane with two states. It is the same “best ending here” dynamic programming idea as Maximum Subarray, with a second state for the minimum.
4. Prefix/suffix view. Between zeros, the best product is always a prefix or a suffix of that segment (an even number of negatives, or dropping everything up to the first or after the last negative). Scanning running products from both ends gives another O(n) solution.

Edge Cases

1. Single negative element: [-7] returns -7; the answer must be a non-empty subarray, so do not default to 0.
2. All zeros and negatives: [-3,0,-5] returns 0.
3. Even number of negatives: [-2,-3,-4] returns 12 from [-3,-4], while [-2,-3] gives only 6.
4. Zeros in the middle: [2,3,0,4,5] returns 20; the zero splits the array into two independent pieces.
5. Large products: [10,10,10,10,10,10,10,10,10] returns 1000000000, close to the 32-bit limit but inside it.

Common Mistakes

1. Tracking only the maximum. Plain Kadane’s on products fails on [-2,5,-3], where the answer 30 comes from the earlier minimum -10 times -3.
2. Updating curMax before computing curMin without a swap or temp. Writing curMax = max(x, curMax*x, curMin*x) and then curMin = min(x, curMax*x, curMin*x) uses the already-overwritten curMax. Save the old value or swap first.
3. Initialising best to 0. That returns 0 for [-7]. Start from nums[0].
4. Resetting to 1 on zero and forgetting the zero itself. If you reset after a zero, still count 0 as a candidate answer, or [-1,0,-2] returns the wrong value.
5. Ignoring overflow assumptions. The problem guarantees every subarray product fits in 32 bits; without that guarantee you would need 64-bit or big-integer arithmetic.

Interview Tips

1. Start from Maximum Subarray. Say “this looks like Kadane’s”, then explain why one running value is not enough for products. That shows you can adapt a known pattern instead of memorising it.
2. Walk through [-2,5,-3] out loud. It shows the minimum turning into the maximum in three steps.
3. Explain zeros explicitly. Interviewers often probe what happens at a zero; the “start fresh” term answers it.
4. Offer the prefix/suffix trick as an alternative if asked for another O(n) method.

Follow-up Questions

1. Return the subarray itself, not only the product: record the start index whenever a “start fresh” choice wins, and the end index whenever best improves.
2. No overflow guarantee: use 64-bit integers, big integers, or compare logarithms of absolute values while tracking the sign.
3. Maximum sum subarray (LC 53): the same pattern with a single running value.
4. Subarray product less than k (LC 713): with positive numbers only, a sliding window counts subarrays in O(n).
5. Circular array: for sums you combine the max subarray with total minus the min subarray; ask how that idea changes for products.

Related Problems

• Maximum Subarray Sum
• Product of Array Except Self
• Best Time to Buy and Sell Stock
• House Robber