LeetCode 152 - Maximum Product Subarray

LeetCode Problem 152

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks us to find the contiguous subarray within an integer array nums that produces the largest possible product. Unlike the classic maximum subarray sum problem, multiplication introduces additional complexity because negative numbers can completely change the result.

A subarray must consist of contiguous elements. We cannot skip elements or rearrange them. The goal is to return the numerical value of the maximum product, not the subarray itself.

The input is an array of integers where:

• The array length is between 1 and 2 * 10^4
• Each element is between -10 and 10
• The final answer always fits inside a signed 32-bit integer

The relatively large array size immediately suggests that an O(n^2) or O(n^3) solution may be too slow. Since n can be as large as 20,000, we should aim for a linear time solution if possible.

The important complication comes from negative numbers and zeros.

A positive number increases a product. A negative number flips the sign of the product. Two negative numbers multiplied together become positive again. This means that the smallest negative product seen so far can suddenly become the largest positive product when multiplied by another negative number.

Zeros are also important because any product containing zero becomes zero. A zero effectively breaks the array into independent segments.

Several edge cases are important:

• Arrays containing only one element
• Arrays containing zeros
• Arrays with an even number of negatives
• Arrays with an odd number of negatives
• Arrays where the maximum product comes from a single element
• Arrays where the optimal subarray is not the longest one

For example:

• [2,3,-2,4] has answer 6
• [-2,3,-4] has answer 24
• [0,2] has answer 2
• [-2] has answer -2

Understanding how negative values affect multiplication is the key insight for solving this problem efficiently.

Approaches

Brute Force Approach

The most straightforward solution is to examine every possible subarray and compute its product.

For each starting index i, we can expand the subarray one element at a time toward the right, maintaining the running product. Every time we extend the subarray, we compare the current product against the global maximum.

This works because every contiguous subarray is explicitly considered, so the maximum product cannot be missed.

However, there are O(n^2) possible subarrays. Even if we compute products incrementally, the total runtime becomes quadratic.

With n = 20,000, an O(n^2) solution could require hundreds of millions of operations, which is too slow for LeetCode constraints.

Optimal Dynamic Programming Approach

The key observation is that multiplication by a negative number can completely reverse the situation.

At each position, we care about two values:

• The maximum product ending at the current position
• The minimum product ending at the current position

The minimum product is important because multiplying a large negative value by another negative value can produce a huge positive product.

For example:

Current number = -4
Previous max = 3
Previous min = -6

New max = max(-4, 3 * -4, -6 * -4)
         = max(-4, -12, 24)
         = 24

This means we must track both extremes simultaneously.

At every element:

• If the current number is positive, the previous maximum remains useful
• If the current number is negative, the previous minimum may become the new maximum
• If the current number is zero, the chain effectively restarts

This leads to a clean O(n) dynamic programming solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every possible subarray product
Optimal	O(n)	O(1)	Tracks both maximum and minimum products ending at each index

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

1. Initialize three variables using the first element of the array:

• current_max
• current_min
• global_max

We use the first element because every subarray must contain at least one number. 2. Iterate through the array starting from index 1. 3. For each number num, first check whether it is negative.

If the current number is negative, multiplying by it swaps the roles of maximum and minimum products. Therefore, swap:

• current_max
• current_min

4. Compute the new maximum product ending at the current index.

The new maximum can come from:

• Starting a new subarray with num
• Extending the previous maximum product
• Extending the previous minimum product if num is negative

So:

current_max = max(num, current_max * num)

5. Compute the new minimum product ending at the current index.

Similarly:

current_min = min(num, current_min * num)

6. Update the global answer.

global_max = max(global_max, current_max)

7. Continue until the end of the array.
8. Return global_max.

Why it works

The algorithm maintains an invariant:

• current_max always stores the maximum product of any subarray ending at the current index
• current_min always stores the minimum product of any subarray ending at the current index

Because multiplication by a negative number reverses ordering, the previous minimum may become the new maximum. By tracking both values at every step, we guarantee that every possible optimal subarray product is considered.

Since every subarray ending at each position is represented implicitly through these transitions, the final global_max must be the largest product overall.

Python Solution

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        current_max = nums[0]
        current_min = nums[0]
        global_max = nums[0]

        for num in nums[1:]:
            if num < 0:
                current_max, current_min = current_min, current_max

            current_max = max(num, current_max * num)
            current_min = min(num, current_min * num)

            global_max = max(global_max, current_max)

        return global_max

The solution begins by initializing all tracking variables with the first element. This ensures that single element arrays are handled naturally without requiring special logic later.

The loop processes each remaining element exactly once.

When the current number is negative, the previous maximum and minimum products swap roles. A large positive product multiplied by a negative becomes a large negative product, while a large negative product multiplied by a negative becomes a large positive product. Swapping the variables before updating simplifies the logic considerably.

After the possible swap, we compute:

• The best positive product ending at this position
• The worst negative product ending at this position

The algorithm also considers starting a completely new subarray at the current element. This is why num itself is included in the max and min calculations.

Finally, global_max keeps track of the largest product seen anywhere in the array.

Go Solution

func maxProduct(nums []int) int {
	currentMax := nums[0]
	currentMin := nums[0]
	globalMax := nums[0]

	for i := 1; i < len(nums); i++ {
		num := nums[i]

		if num < 0 {
			currentMax, currentMin = currentMin, currentMax
		}

		currentMax = max(num, currentMax*num)
		currentMin = min(num, currentMin*num)

		globalMax = max(globalMax, currentMax)
	}

	return globalMax
}

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
}

The Go implementation follows exactly the same logic as the Python version.

Since Go does not provide built in max and min functions for integers, helper functions are implemented manually.

The problem guarantees that all products fit within a 32-bit signed integer, so standard Go int arithmetic is sufficient for LeetCode.

The array is guaranteed to contain at least one element, so accessing nums[0] is always safe.

Worked Examples

Example 1

Input:

nums = [2,3,-2,4]

Initial state:

Index	Num	current_max	current_min	global_max
0	2	2	2	2

Process 3:

Index	Num	current_max	current_min	global_max
1	3	max(3, 2×3)=6	min(3, 2×3)=3	6

Process -2:

Before update, swap max/min because number is negative.

Index	Num	current_max	current_min	global_max
2	-2	max(-2, 3×-2)=-2	min(-2, 6×-2)=-12	6

Process 4:

Index	Num	current_max	current_min	global_max
3	4	max(4, -2×4)=4	min(4, -12×4)=-48	6

Final answer:

6

Example 2

Input:

nums = [-2,0,-1]

Initial state:

Index	Num	current_max	current_min	global_max
0	-2	-2	-2	-2

Process 0:

Index	Num	current_max	current_min	global_max
1	0	max(0, -2×0)=0	min(0, -2×0)=0	0

Process -1:

Swap first because number is negative.

Index	Num	current_max	current_min	global_max
2	-1	max(-1, 0×-1)=0	min(-1, 0×-1)=-1	0

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(1)	Only a few variables are stored regardless of input size

The algorithm performs a constant amount of work per element in the array. No nested loops or auxiliary data structures are used.

Space usage remains constant because the solution only tracks the current maximum product, current minimum product, and global maximum.

Test Cases

solution = Solution()

assert solution.maxProduct([2, 3, -2, 4]) == 6  # basic example
assert solution.maxProduct([-2, 0, -1]) == 0  # zero breaks product chain
assert solution.maxProduct([-2]) == -2  # single negative element
assert solution.maxProduct([5]) == 5  # single positive element
assert solution.maxProduct([0]) == 0  # single zero
assert solution.maxProduct([-2, 3, -4]) == 24  # two negatives create large positive
assert solution.maxProduct([2, -5, -2, -4, 3]) == 24  # multiple sign changes
assert solution.maxProduct([-1, -2, -3, -4]) == 24  # even number of negatives
assert solution.maxProduct([-1, -2, -3]) == 6  # odd number of negatives
assert solution.maxProduct([0, 2]) == 2  # restart after zero
assert solution.maxProduct([-2, 0, -1, -3]) == 3  # best subarray after zero
assert solution.maxProduct([1, 2, 3, 4]) == 24  # all positive
assert solution.maxProduct([-10, -10, 5, 2]) == 1000  # large positive from negatives
assert solution.maxProduct([3, -1, 4]) == 4  # single element best
assert solution.maxProduct([-2, -3, 7]) == 42  # entire array optimal

Test	Why
[2,3,-2,4]	Standard example with negative interruption
[-2,0,-1]	Tests zero splitting behavior
[-2]	Single negative element
[5]	Single positive element
[0]	Single zero
[-2,3,-4]	Negative pair creates maximum
[2,-5,-2,-4,3]	Multiple sign flips
[-1,-2,-3,-4]	Even number of negatives
[-1,-2,-3]	Odd number of negatives
[0,2]	Restart after zero
[-2,0,-1,-3]	Best product occurs after reset
[1,2,3,4]	Pure positive multiplication
[-10,-10,5,2]	Large positive from two negatives
[3,-1,4]	Single value becomes optimal
[-2,-3,7]	Entire array forms maximum product

Edge Cases

Arrays Containing Zero

Zeros are especially important because multiplication by zero resets the product completely. A naive implementation might incorrectly continue multiplying across zero boundaries.

For example:

[-2, 0, -1]

The subarray [-2, -1] is not valid because the elements are not contiguous after the zero. The implementation handles this naturally because when num == 0, both current_max and current_min become zero, effectively restarting the computation.

Arrays With Multiple Negative Numbers

Negative values are the main challenge in this problem. A naive greedy strategy that only tracks the current maximum product fails because a very negative product may later become the largest positive product.

For example:

[-2, 3, -4]

At index 1, the running product becomes negative. However, multiplying by -4 later converts it into a large positive value.

The implementation solves this by tracking both:

• The maximum product ending at each position
• The minimum product ending at each position

This guarantees that future negative numbers are handled correctly.

Single Element Arrays

The array may contain only one number.

Examples:

[5]
[-2]
[0]

Some implementations incorrectly initialize values to 0 or 1, which breaks these cases.

This solution initializes all tracking variables using nums[0], ensuring that single element inputs are handled correctly without any special conditional logic.