Maximum Product of a Contiguous Subarray With Negatives and Zeros
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: Given an integer array that may contain negative numbers and zeros, return the largest product of any non-empty contiguous subarray. The problem tests careful reasoning about sign changes, zeros and single-element subarrays under tight input-size limits.
Read the full LinkedIn Software Engineer interview experience this question came from
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.
### 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 as an integer, 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`.
Because of the last constraint, every subarray product and the answer fit in a signed 32-bit integer (`int` in Java and C++); no value exceeds `2^31 - 1`.
### Examples
**Example 1**
```text
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**
```text
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**
```text
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.
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, so every subarray product and the answer fit in a signed 32-bit integer
Examples
Input: ([3, -1, 4, 2],)
Expected Output: 8
Explanation: Source Example 1: [4, 2] gives 8; every subarray containing -1 is negative.
Input: ([-2, 5, -3, 0, 7],)
Expected Output: 30
Explanation: Source Example 2: the two negatives cancel in [-2, 5, -3]; a max-only Kadane returns 7.
Hints
- A negative factor flips the sign of a product: a subarray with a large negative product can become the best one after one more negative number, as in Example 2.
- Every subarray that contains a 0 has product 0, so zeros split the array into independent parts, yet 0 itself can still be the answer when every other product is negative.
- A single element is a valid subarray, so an array holding one negative number returns that number, not 0.