# The Multiplier Rush

> Negatives cancel negatives - but only if you keep both in view.

Canonical URL: <https://datadriven.io/problems/the_multiplier_rush>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a list of integers, return the maximum product achievable by any contiguous subarray. Account for negative numbers, which can flip sign when multiplied.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **dynamic programming with sign tracking**, extending the classic maximum subarray sum problem (Kadane's algorithm) to handle multiplication. Negative numbers can flip the sign of products, requiring both max and min tracking at each step.

> **Trick to Solving**
>
> Track both the current maximum and minimum product ending at each position. A negative number turns the maximum into the minimum and vice versa. At each step, consider `num`, `num * max_so_far`, and `num * min_so_far` to handle all sign combinations.

---

### Break down the requirements

#### Step 1: Track running max and min products

At each position, maintain the maximum and minimum product of any subarray ending here. The min is needed because it could become the max after multiplying by a negative number.

#### Step 2: Update both at each element

The new max is the largest of `num`, `num * prev_max`, `num * prev_min`. The new min is the smallest of the same three.

#### Step 3: Track the global maximum

Update the overall answer whenever the local max exceeds it.

---

### The solution

**Modified Kadane's with min/max product tracking**

```python
def max_product_subarray(nums):
    if not nums:
        return 0
    global_max = nums[0]
    local_max = nums[0]
    local_min = nums[0]
    for i in range(1, len(nums)):
        num = nums[i]
        candidates = [num, num * local_max, num * local_min]
        local_max = max(candidates)
        local_min = min(candidates)
        if local_max > global_max:
            global_max = local_max
    return global_max
```

> **Time and Space Complexity**
>
> **Time:** O(n) with a single pass.
> 
> **Space:** O(1). Only three tracking variables.

> **Interviewers Watch For**
>
> Can you explain why tracking the minimum is essential? Without it, a sequence like `[-2, 3, -4]` would miss that `-2 * 3 * -4 = 24` because the negative product at index 1 becomes the source of the global max at index 2.

> **Common Pitfall**
>
> Computing `local_max` and `local_min` sequentially using the updated value. You must compute both from the *previous* values. Using `candidates` avoids this by computing from the pre-update state.

---

## Common follow-up questions

- What if you also needed to return the actual subarray? _(Tests tracking start and end indices alongside the product.)_
- How does this differ from maximum subarray sum (Kadane's)? _(Tests understanding that addition has no sign-flipping problem, so only max tracking is needed.)_
- What if the array contained zeros? _(Tests that zero resets both local_max and local_min to 0, effectively starting a new subarray.)_
- What if the product could overflow in a language without arbitrary precision? _(Tests awareness of numerical limits and when to use logarithms.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_multiplier_rush)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.