Problem Description

You are given an integer array nums. Your task is to find a contiguous subarray within this array that produces the largest product when all its elements are multiplied together, and return that maximum product.

A subarray is a contiguous sequence of elements from the array (it must contain at least one element). For example, if nums = [2, 3, -2, 4], some possible subarrays are [2], [2, 3], [3, -2, 4], and the entire array [2, 3, -2, 4].

The challenge involves handling both positive and negative numbers. Negative numbers can flip the sign of the product, which means a very negative product could become very positive if multiplied by another negative number.

For instance:

• If nums = [2, 3, -2, 4], the subarray [2, 3] gives the maximum product of 6
• If nums = [-2, 0, -1], the maximum product is 0 (from the subarray [0])
• If nums = [-2, 3, -4], the maximum product is 24 (from the entire array, as -2 × 3 × -4 = 24)

The solution uses dynamic programming with two tracking variables:

• f tracks the maximum product ending at the current position
• g tracks the minimum product ending at the current position (important because a minimum negative value could become maximum when multiplied by another negative)

At each position, the algorithm considers three possibilities:

1. Start a new subarray from the current element x
2. Extend the previous maximum product by multiplying with x
3. Extend the previous minimum product by multiplying with x (useful when x is negative)

The answer is guaranteed to fit within a 32-bit integer range.

Intuition

The key insight is that when dealing with products, negative numbers create an interesting dynamic - they can flip our results from very bad to very good (or vice versa). A large negative product becomes a large positive product when multiplied by another negative number.

Consider why a greedy approach of just keeping the maximum product won't work. If we have [-2, 3, -4], after processing -2 and 3, we'd have a maximum product of 3. But when we encounter -4, if we only tracked the maximum, we'd compute 3 × -4 = -12 and miss that -6 × -4 = 24 is actually better. The -6 came from -2 × 3, which was our minimum at that point.

This leads us to realize we need to track both the maximum AND minimum products ending at each position. Why? Because:

• The minimum (most negative) product could become the maximum when multiplied by a negative number
• The maximum product could become the minimum when multiplied by a negative number

At each position, we have three choices:

1. Start fresh with just the current element (useful when previous products are worse than the element itself, like when we hit a 0 or when signs don't work in our favor)
2. Extend the previous maximum by multiplying with the current element
3. Extend the previous minimum by multiplying with the current element

By considering all three options and taking the appropriate max/min at each step, we ensure we don't miss any potential maximum product. The variables f and g act as our dynamic programming states, where f represents "what's the best product I can get ending here" and g represents "what's the worst product I can get ending here" - both of which might be useful for future calculations.

This approach elegantly handles all edge cases including zeros (which reset our product), negative numbers (which can flip our fortunes), and ensures we find the global maximum across all possible subarrays.

Solution Approach

The implementation uses a dynamic programming approach with space optimization, tracking two key values at each position:

• f: maximum product ending at current position
• g: minimum product ending at current position

Let's walk through the algorithm step by step:

Initialization:

ans = f = g = nums[0]

We initialize all three variables with the first element. ans will track our global maximum, while f and g track the current maximum and minimum products.

Main Loop:

for x in nums[1:]:

We iterate through the array starting from the second element.

Store Previous Values:

ff, gg = f, g

Before updating f and g, we store their previous values since we need them for calculations.

Update Maximum and Minimum:

f = max(x, ff * x, gg * x)
g = min(x, ff * x, gg * x)

For each element x, we calculate:

• New maximum f: the largest among:
  • x (start new subarray)
  • ff * x (extend previous maximum)
  • gg * x (extend previous minimum - useful when x is negative)
• New minimum g: the smallest among the same three values

Update Global Maximum:

ans = max(ans, f)

We continuously update our answer with the maximum product found so far.

Example Walkthrough with nums = [2, 3, -2, 4]:

1. Initialize: ans = f = g = 2
2. Process 3:
   • f = max(3, 2*3, 2*3) = 6
   • g = min(3, 2*3, 2*3) = 3
   • ans = max(2, 6) = 6
3. Process -2:
   • f = max(-2, 6*(-2), 3*(-2)) = max(-2, -12, -6) = -2
   • g = min(-2, 6*(-2), 3*(-2)) = min(-2, -12, -6) = -12
   • ans = max(6, -2) = 6
4. Process 4:
   • f = max(4, -2*4, -12*4) = max(4, -8, -48) = 4
   • g = min(4, -2*4, -12*4) = min(4, -8, -48) = -48
   • ans = max(6, 4) = 6

The algorithm correctly identifies that the maximum product subarray is [2, 3] with product 6.

Time Complexity: O(n) - single pass through the array
Space Complexity: O(1) - only using constant extra space

Example Walkthrough

Let's trace through the algorithm with nums = [-2, 3, -4] to see how tracking both maximum and minimum values helps us find the optimal solution.

Initial State:

• Start with the first element: ans = f = g = -2
• f tracks maximum product ending here: -2
• g tracks minimum product ending here: -2
• ans tracks global maximum: -2

Step 1: Process element 3 (index 1)

• Store previous values: ff = -2, gg = -2
• Calculate new maximum: f = max(3, -2×3, -2×3) = max(3, -6, -6) = 3
  • We choose to start fresh with 3 rather than extend with -6
• Calculate new minimum: g = min(3, -2×3, -2×3) = min(3, -6, -6) = -6
  • The minimum is -6 from extending the previous product
• Update global max: ans = max(-2, 3) = 3

Step 2: Process element -4 (index 2)

• Store previous values: ff = 3, gg = -6
• Calculate new maximum: f = max(-4, 3×(-4), -6×(-4)) = max(-4, -12, 24) = 24
  • The key insight: multiplying the minimum -6 by negative -4 gives us 24!
• Calculate new minimum: g = min(-4, 3×(-4), -6×(-4)) = min(-4, -12, 24) = -12
  • The minimum is now -12 from extending the previous maximum
• Update global max: ans = max(3, 24) = 24

Result: The maximum product is 24 from the subarray [-2, 3, -4]

This example perfectly demonstrates why we need to track the minimum: at step 2, the previous minimum value -6 (which seemed "bad") became crucial for finding the maximum product when multiplied by the negative number -4. Without tracking the minimum, we would have missed this optimal solution and incorrectly returned 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input array nums. The algorithm iterates through the array exactly once (starting from index 1), performing a constant number of operations for each element. The operations inside the loop (max, min, multiplication, and assignment) all take O(1) time.

Space Complexity: O(1). The algorithm uses only a fixed amount of extra space regardless of the input size. The variables ans, f, g, ff, and gg are the only additional storage used, and they don't scale with the input size. No additional data structures like arrays or recursion stacks are used.

Common Pitfalls

Pitfall 1: Not Tracking Both Maximum and Minimum

The Problem: A common mistake is only tracking the maximum product ending at each position, similar to the classic maximum subarray sum problem (Kadane's algorithm). This approach fails when dealing with negative numbers.

Why It Fails: Consider nums = [-2, 3, -4]. If we only track the maximum:

• At -2: max = -2
• At 3: max = max(3, -2 * 3) = 3
• At -4: max = max(-4, 3 * -4) = -4

This gives us -4, but the actual answer is 24 (from multiplying all three numbers).

The Fix: Always track both maximum AND minimum products. The minimum (most negative) value can become the maximum when multiplied by a negative number:

# WRONG: Only tracking maximum
max_ending = nums[0]
result = nums[0]
for num in nums[1:]:
    max_ending = max(num, max_ending * num)
    result = max(result, max_ending)

# CORRECT: Tracking both maximum and minimum
max_ending = min_ending = result = nums[0]
for num in nums[1:]:
    temp_max = max_ending
    max_ending = max(num, max_ending * num, min_ending * num)
    min_ending = min(num, temp_max * num, min_ending * num)
    result = max(result, max_ending)

Pitfall 2: Forgetting to Store Previous Values Before Updating

The Problem: When updating max_ending_here and min_ending_here, you need the previous values of both. If you update max_ending_here first without storing its previous value, you'll use the wrong value when calculating min_ending_here.

Why It Fails:

# WRONG: Using updated max_ending_here to calculate min_ending_here
for num in nums[1:]:
    max_ending_here = max(num, max_ending_here * num, min_ending_here * num)
    min_ending_here = min(num, max_ending_here * num, min_ending_here * num)  # Bug!

In the second line, max_ending_here has already been updated, so we're not using the previous maximum.

The Fix: Store the previous values before any updates:

# CORRECT: Store previous values first
for num in nums[1:]:
    prev_max = max_ending_here
    prev_min = min_ending_here
    max_ending_here = max(num, prev_max * num, prev_min * num)
    min_ending_here = min(num, prev_max * num, prev_min * num)

Pitfall 3: Handling Arrays with Zeros Incorrectly

The Problem: Some implementations try to handle zeros as special cases by splitting the array at zero positions. While this can work, it adds unnecessary complexity.

Why It's Unnecessary: The standard algorithm handles zeros naturally. When we encounter a zero:

• max_ending_here = max(0, prev_max * 0, prev_min * 0) = 0
• min_ending_here = min(0, prev_max * 0, prev_min * 0) = 0

This effectively "resets" both trackers, which is exactly what we want - the product including a zero is always 0, so we essentially start fresh from the next element.

The Better Approach: Let the algorithm handle zeros naturally without special cases:

# No need for special zero handling
for num in nums[1:]:
    prev_max = max_ending_here
    prev_min = min_ending_here
    max_ending_here = max(num, prev_max * num, prev_min * num)
    min_ending_here = min(num, prev_max * num, prev_min * num)
    max_product = max(max_product, max_ending_here)

The algorithm automatically "breaks" the subarray at zeros and continues, making explicit zero-handling unnecessary.