Maximum Product of a Contiguous Subarray With Negatives and Zeros

Given an integer array nums, return the largest product obtained by multiplying the elements of a non-empty contiguous subarray. The array can contain negative numbers and zeros.

Function Signature

def max_subarray_product(nums: list[int]) -> int:

Rules

• A subarray is a non-empty run of consecutive elements; a single element is a valid subarray.
• The product of a subarray multiplies all of its elements, including any zeros and negative numbers.
• Return only the largest product, not the subarray. If several subarrays reach it, the returned value is the same.

Constraints

• 1 <= len(nums) <= 2 * 10^4
• -10 <= nums[i] <= 10
• the product of every contiguous subarray of nums lies between -2^31 and 2^31 - 1

Examples

Example 1

Input: nums = [3, -1, 4, 2]
Output: 8

The subarray [4, 2] gives 8. Every subarray that contains -1 has a negative product.

Example 2

Input: nums = [-2, 5, -3, 0, 7]
Output: 30

(-2) × 5 × (-3) = 30: the two negatives cancel. Any subarray that reaches the 0 has product 0, and [7] gives only 7.

Example 3

Input: nums = [-1, -2, -3]
Output: 6

The whole array has three negatives and a product of -6; leaving out -1 gives [-2, -3] with product 6.