# LeetCode 152: Maximum Product Subarray

## Problem Restatement

We are given an integer array `nums`.

We need to find a contiguous non-empty subarray whose product is as large as possible.

Return the maximum product.

A subarray must contain consecutive elements from the original array.

For example:

```python
nums = [2, 3, -2, 4]
```

The subarray:

```python
[2, 3]
```

has product:

```python
2 * 3 = 6
```

The full array product is:

```python
2 * 3 * -2 * 4 = -48
```

So the answer is:

```python
6
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Maximum product of a contiguous subarray |
| Constraint | Subarray must be non-empty |
| Important detail | Numbers may be positive, negative, or zero |

Example function shape:

```python
def maxProduct(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [2, 3, -2, 4]
```

Possible products:

| Subarray | Product |
|---|---|
| `[2]` | `2` |
| `[2, 3]` | `6` |
| `[3, -2]` | `-6` |
| `[-2, 4]` | `-8` |

The largest product is:

```python
6
```

Example 2:

```python
nums = [-2, 0, -1]
```

Possible products:

| Subarray | Product |
|---|---|
| `[-2]` | `-2` |
| `[0]` | `0` |
| `[-1]` | `-1` |
| `[-2, 0]` | `0` |

The maximum product is:

```python
0
```

Example 3:

```python
nums = [-2, 3, -4]
```

The full product is:

```python
(-2) * 3 * (-4) = 24
```

So the answer is:

```python
24
```

## First Thought: Brute Force

The simplest solution is to try every possible subarray.

For every starting position `i`, compute the product while extending the subarray to the right.

Code:

```python
class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        n = len(nums)
        best = nums[0]

        for i in range(n):
            product = 1

            for j in range(i, n):
                product *= nums[j]
                best = max(best, product)

        return best
```

This works because every contiguous subarray is checked exactly once.

## Problem With Brute Force

If the array has `n` elements, there are about:

$$
\frac{n(n+1)}{2}
$$

possible subarrays.

So the brute force algorithm runs in:

```python
O(n^2)
```

time.

We need a faster method.

## Key Insight

This problem becomes tricky because of negative numbers.

A negative number can completely change the result.

For example:

```python
2 * 3 = 6
```

but:

```python
2 * 3 * (-2) = -12
```

Then multiplying by another negative number flips the sign again:

```python
2 * 3 * (-2) * (-4) = 48
```

So while scanning the array, we must track:

1. The largest product ending at the current position
2. The smallest product ending at the current position

The smallest product matters because multiplying two negative numbers can become a very large positive number.

## Dynamic Programming State

At each index:

| Variable | Meaning |
|---|---|
| `max_prod` | Maximum product ending here |
| `min_prod` | Minimum product ending here |
| `answer` | Best product seen so far |

When we read a new number `x`, three possibilities exist:

1. Start a new subarray with `x`
2. Extend the previous maximum product
3. Extend the previous minimum product

So the transitions are:

$$
\text{newMax}=\max(x,\;x\cdot\text{maxProd},\;x\cdot\text{minProd})
$$

and:

$$
\text{newMin}=\min(x,\;x\cdot\text{maxProd},\;x\cdot\text{minProd})
$$

## Algorithm

Initialize:

```python
max_prod = nums[0]
min_prod = nums[0]
answer = nums[0]
```

Then scan from left to right.

For each number:

1. Compute possible products
2. Update maximum product ending here
3. Update minimum product ending here
4. Update global answer

## Correctness

At every position `i`, `max_prod` stores the largest product among all subarrays ending at index `i`.

Similarly, `min_prod` stores the smallest product among all subarrays ending at index `i`.

Any subarray ending at `i` must either:

1. Start at `i`
2. Extend a subarray ending at `i - 1`

Therefore the only possible products are:

```python
nums[i]
nums[i] * previous_max
nums[i] * previous_min
```

Taking the maximum of these gives the best product ending at `i`.

Taking the minimum gives the worst product ending at `i`.

Because every subarray must end somewhere, tracking the best value across all positions guarantees the global maximum product.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | Only a few variables are stored |

## Implementation

```python
class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        max_prod = nums[0]
        min_prod = nums[0]
        answer = nums[0]

        for num in nums[1:]:
            candidates = (
                num,
                num * max_prod,
                num * min_prod,
            )

            max_prod = max(candidates)
            min_prod = min(candidates)

            answer = max(answer, max_prod)

        return answer
```

## Code Explanation

We begin with the first number:

```python
max_prod = nums[0]
min_prod = nums[0]
answer = nums[0]
```

For every next number, we compute all possible ways to form a subarray ending here:

```python
candidates = (
    num,
    num * max_prod,
    num * min_prod,
)
```

A negative number may turn the previous minimum into the new maximum.

So we must compute both.

Then we update:

```python
max_prod = max(candidates)
min_prod = min(candidates)
```

Finally:

```python
answer = max(answer, max_prod)
```

stores the best result seen so far.

## Alternative Optimization

Some implementations swap the variables when the current number is negative.

Example:

```python
if num < 0:
    max_prod, min_prod = min_prod, max_prod
```

Then:

```python
max_prod = max(num, num * max_prod)
min_prod = min(num, num * min_prod)
```

This avoids creating a temporary tuple.

Both versions are correct.

## Testing

```python
def run_tests():
    sol = Solution()

    assert sol.maxProduct([2, 3, -2, 4]) == 6
    assert sol.maxProduct([-2, 0, -1]) == 0
    assert sol.maxProduct([-2, 3, -4]) == 24
    assert sol.maxProduct([0, 2]) == 2
    assert sol.maxProduct([-2]) == -2
    assert sol.maxProduct([-1, -2, -3]) == 6
    assert sol.maxProduct([2, -5, -2, -4, 3]) == 24

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[2, 3, -2, 4]` | Standard example |
| `[-2, 0, -1]` | Zero resets products |
| `[-2, 3, -4]` | Two negatives become positive |
| `[0, 2]` | Single positive after zero |
| `[-2]` | Single-element array |
| `[-1, -2, -3]` | Odd number of negatives |
| `[2, -5, -2, -4, 3]` | Multiple sign changes |