LeetCode 152 - Maximum Product Subarray

Given an integer array nums, this Medium dynamic programming problem asks for the largest product among all contiguous non-empty subarrays. Because multiplying two negative numbers flips their sign into a positive product, I tracked both the running maximum and minimum products at each index in a single O(n) pass.

---

Problem link and explanation

• Problem: 152. Maximum Product Subarray
• Summary: Find the contiguous subarray within nums that has the largest product, and return that product.

Unlike maximum sum problems (Kadane’s Algorithm), the product of two small negative numbers can yield a large positive number. Maintaining only the maximum product loses essential context when the next number is negative. Retaining the minimum running product guarantees that a negative-to-positive transition is captured correctly.

---

Approach

Maintain cur_max and cur_min as running accumulators up to the current index.

res = nums[0]
cur_max = nums[0]
cur_min = nums[0]

for i in range(1, len(nums)):
    num = nums[i]

    if num < 0:
        tmp = cur_max
        cur_max = cur_min
        cur_min = tmp

    cur_max = max(num, cur_max * num)
    cur_min = min(num, cur_min * num)

    res = max(res, cur_max)

1. Negative swap: When the incoming number num is negative, the potential maximum and minimum values invert. Swapping cur_max and cur_min upfront aligns the values for multiplication.
2. State transitions:
   • The new cur_max is the maximum between starting a new subarray at num and extending the previous product cur_max * num.
   • The new cur_min is the minimum between num and cur_min * num.
3. Global update: Update the answer res with the highest cur_max seen across all steps.

---

Complexity analysis

• Time complexity: O(n)
  • Traverses the array once with constant-time arithmetic and comparison operations per element.
• Space complexity: O(1)
  • Operates with only three scalar variables without allocating auxiliary DP arrays.

---

Implementation code

class Solution:

    def maxProduct(self, nums) -> int:
        if not nums:
            return 0

        res = nums[0]
        cur_max = nums[0]
        cur_min = nums[0]

        for i in range(1, len(nums)):
            num = nums[i]

            if num < 0:
                tmp = cur_max
                cur_max = cur_min
                cur_min = tmp

            cur_max = max(num, cur_max * num)
            cur_min = min(num, cur_min * num)

            res = max(res, cur_max)

        return res

---

Summary and reflection

The key invariant in the maximum product subarray problem is that extreme values can switch roles instantly upon encountering a negative coefficient. Swapping the running minimum and maximum whenever a negative number arrives eliminates nested conditional logic, keeping the DP transition clean and linear.