Maximum Product Subarray

Medium Problem 120 of 151 Java and Python

Practice on LeetCode

Problem

Given an integer array nums, find a contiguous non-empty subarray with the largest product, and return that product.

Example 1

Input: nums = [2, 3, -2, 4]
Output: 6
Why: [2, 3].

Example 2

Input: nums = [-2, 0, -1]
Output: 0

Example 3

Input: nums = [-2, 3, -4]
Output: 24
Why: Two negatives make a positive.

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
The answer fits in a 32-bit integer.

Explanation

Kadane's idea almost works, but a negative number flips signs: the smallest (most negative) product so far becomes the largest when multiplied by a negative.

So track both the largest and the smallest product of a subarray ending at the current index.

Approach 1 · Naive

Every subarray

Time O(n²)
Space O(1)

Fix each start and extend the end, keeping a running product.

For each i, product = 1; for each j ≥ i, multiply by nums[j] and update the best.

Java

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

Python

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

Approach 2 · Optimal

Track the max and min ending here

Time O(n)
Space O(1)

For each number, the new max and min are among x, x × oldMax and x × oldMin.

Start high = low = best = nums[0].
For each later x: compute candidates x, x * high, x * low; set high to the largest and low to the smallest.
Update best = max(best, high).

Java

class Solution {
    public int maxProduct(int[] nums) {
        int high = nums[0];
        int low = nums[0];
        int best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            int a = x * high;
            int b = x * low;
            high = Math.max(x, Math.max(a, b));
            low = Math.min(x, Math.min(a, b));
            best = Math.max(best, high);
        }
        return best;
    }
}

Python

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        high = low = best = nums[0]
        for x in nums[1:]:
            candidates = (x, x * high, x * low)
            high, low = max(candidates), min(candidates)
            best = max(best, high)
        return best

Complexity compared

Approach	Time	Space
Naive Every subarray	O(n²)	O(1)
Optimal Track the max and min ending here	O(n)	O(1)

Key takeaways

Compute both new values from the old high and low; updating high first and then using it for low is a classic bug.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem