Maximum Product Subarray

Given an integer array nums, find a subarray that has the largest product within the array and return it.

A subarray is a contiguous non-empty sequence of elements within an array.

You can assume the output will fit into a 32-bit integer.

Approach

Track both the maximum and minimum product ending at each position, because multiplying by a negative number swaps them. Update these values as you scan the array and keep the global maximum.

Why It Works

The maximum product subarray ending at index i is either the current number alone or the current number times the previous max/min (depending on sign). Tracking both extremes captures all possibilities, and the global maximum over all endings is the answer.

Complexity

• Time: O(n)
• Space: O(1)

Reference Implementation (Python)

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max_prod = min_prod = ans = nums[0]
        for num in nums[1:]:
            if num < 0:
                max_prod, min_prod = min_prod, max_prod
            max_prod = max(num, max_prod * num)
            min_prod = min(num, min_prod * num)
            ans = max(ans, max_prod)
        return ans