💬 Discord
Sign In
NeetCode #670LC-152Medium1-D Dynamic ProgrammingBlind 75NC 150NC 250
← Back to All Problems

#670 · #152 · Maximum Product Subarray(乘积最大子数组)

📌 Problem Statement & Constraints

Given an integer array nums, find a contiguous subarray with the largest product and return that product. Constraints: 1 <= nums.length <= 2 * 10^4, -10 <= nums[i] <= 10, and the answer fits in a 32-bit integer.

💡 Core Algorithmic Approaches

  1. Track both the maximum and the minimum product of a subarray ending at the current position.
  2. The minimum must be tracked because multiplying it by a negative number turns it into the new maximum.
  3. At each element x, the candidates are x, x * cur_max, and x * cur_min; take the max and min of these three.
  4. The global answer is the best maximum seen over the whole scan.

💻 Benchmark Python3 Implementation

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = cur_max = cur_min = nums[0]
        for x in nums[1:]:
            # a negative x swaps the roles of the running max and min
            cand = (x, x * cur_max, x * cur_min)
            cur_max, cur_min = max(cand), min(cand)
            res = max(res, cur_max)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass over the array.
💾 Space Complexity
O(1): three scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Tracking only the maximum product: a negative element flips the sign, so the minimum is essential; [-2, 3, -4] reaches 24 only when the minimum is carried.
  • Resetting to zero on a negative product: unlike sums, a negative running product is not a reason to restart.
  • Initialising the running values to 0: start from nums[0] so that an all-negative array such as [-1] returns -1.
  • Assuming a zero always ends the best subarray: zero is handled naturally by the max, and a later segment may still beat the best.