Domain 2MediumCORE

Maximum Product Subarray

We are given an integer array nums and need to find the contiguous subarray with the largest product. The key constraints here involve handling negative numbers (which flip signs) and zeros (which reset products). We must return a non-empty subarray, so we cannot skip elements entirely if they contribute positively or are necessary for sign flipping.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Dynamic Programming

152. Maximum Product Subarray

Model: qwen3.5:9b
Topics: Array,Dynamic Programming
FAANG asked: 1
Acceptance rate: 32.9%


Problem Breakdown

We are given an integer array nums and need to find the contiguous subarray with the largest product. The key constraints here involve handling negative numbers (which flip signs) and zeros (which reset products). We must return a non-empty subarray, so we cannot skip elements entirely if they contribute positively or are necessary for sign flipping.

  • Inputs: nums (List[int]).
  • Output: Integer representing the maximum product.
  • Tricky Cases:
    • A negative number at index ii might make a previous small negative product become large positive when multiplied by another negative later in the array.
    • Zeros break continuity; any subarray crossing zero has product 0, effectively resetting our running calculation unless we pick just one side of it.

Intuition

A brute-force solution would check every possible start and end index (i,j)(i, j) where j≥ij \ge i, calculate the product for each window, and track the maximum. This is O(N2)O(N^2) or worse depending on implementation, which fails given constraints up to N=20,000N = 20,000.

The key insight comes from Dynamic Programming: To determine the max product ending at index i, we need more than just the previous maximum product. If nums[i] is negative, multiplying it by a large positive number yields a small (negative) result, but multiplying it by a very small (large magnitude negative) number yields a large positive result.

Therefore, for every position i, we must track two values:

  1. The maximum product ending at i.
  2. The minimum product ending at i (to handle the sign flip from negatives).

Approach

We iterate through the array once (O(N)O(N) time complexity). We maintain three variables throughout the loop:

  • max_so_far: Tracks the global maximum found so far.
  • curr_max: The max product of a subarray ending at current index.
  • curr_min: The min product of a subarray ending at current index (needed because multiplying by negative flips them).

At each step, we calculate new values for curr_max and curr_min. Since the order matters (we need previous state), we compute both based on the previous iteration’s max/min. The transition logic is:

  1. If current number is positive: extend existing subarrays or start fresh with this number. Max increases, Min decreases.
  2. If current number is negative: curr_max becomes either just the number (start new) or previous min * number (flip sign). Same for curr_min.

We update max_so_far after calculating each step’s local max. We handle initialization by setting both running variables to the first element of the array before looping from index 1, though initializing with a flag or handling index 0 inside loop works too. I will initialize tracking vars at start and iterate through all elements for cleaner logic.

Complexity Analysis

  • Time: O(N)O(N) - We traverse the input list exactly once.
  • Space: O(1)O(1) - We only use a constant amount of extra variables (curr_max, curr_min, max_so_far) regardless of array size.

Solution

def maxProduct(nums):
    if not nums:
        return 0
    
    # Initialize tracking vars with the first element to handle single-element arrays naturally
    curr_max = nums[0]
    curr_min = nums[0]
    ans = nums[0]

    for i in range(1, len(nums)):
        num = nums[i]
        
        # Calculate potential new max/min. 
        # We must consider: starting fresh (num), extending current_max, or flipping via current_min
        temp_max = max(num, curr_max * num, curr_min * num)
        temp_min = min(num, curr_max * num, curr_min * num)

        # Update running state for next iteration
        curr_max = temp_max
        curr_min = temp_min
        
        # Track global maximum found so far
        ans = max(ans, curr_max)

    return ans

Edge Cases Handled

  • Single Element: The loop starts at index 1; if length is 1, the initialization sets ans to that element and returns immediately.
  • All Negative Numbers: If negatives are present without zeros (e.g., [-2, -3]), curr_min captures -6, then multiplying by next negative flips it back up correctly in temp_max.
  • Zeros: When a zero is encountered (num = 0), both temp_max and temp_min become at least 0 (since max(0, ...)). This effectively resets the subarray product to start fresh after the zero.
  • Mixed Signs: The logic explicitly checks all three possibilities for each step: starting new (num) or extending previous max/min (curr_max * num, curr_min * num), ensuring we don’t miss a sign flip opportunity.