Maximum Product Subarray

Course Schedule II

Counting Bits

Find the largest product obtainable from any non-empty contiguous subarray.

Given an integer array `nums`, return the largest product you can get from any non-empty contiguous subarray.

**Input / output**
- Input: `nums: int[]`
- Output: the maximum product as an integer

**Examples**
1. `nums = [2, 3, -2, 4]` returns `6` because the best subarray is `[2, 3]`.
2. `nums = [-2, 0, -1]` returns `0` because every non-empty subarray has product `-2`, `0`, or `-1`.
3. `nums = [-2, 3, -4]` returns `24` because the whole array multiplies to `24`.

**Constraints**
- `1 <= nums.length <= 20000`
- `-10 <= nums[i] <= 10`
- The answer fits in a 32-bit signed integer.

**Edge cases**
- A negative value can turn the smallest running product into the largest one.
- Zeros split the array into independent segments.
- The best answer may be a single element.

**Target complexity**
- Aim for `O(n)` time and `O(1)` extra space.

**Hints**
1. Track both the largest and smallest product ending at the current index.
2. When the next number is negative, those two running values swap roles.

**Follow-up**
Why is tracking only the current maximum product insufficient once negative numbers are allowed?

- Products behave differently from sums because multiplying by a negative flips the sign.
- A very small negative running product can become the best positive answer after another negative value.

Understand why sign changes matter

- Start each subarray at every index and keep multiplying as you extend the right edge.
- This checks all `O(n^2)` contiguous subarrays and is correct, but too slow for long inputs.

Brute-force every starting point

- Let `max_ending` be the largest product ending at the current index.
- Let `min_ending` be the smallest product ending there, because a future negative number may flip it into the new maximum.

Keep both extremes at each position

- When the current number is negative, swap the running extremes before multiplying.
- Then decide whether to start fresh at `num` or extend the previous product.

Update the running max and min in one pass

Trace `nums = [2, 3, -2, 4]`.

| num | max_ending before | min_ending before | max_ending after | min_ending after | best |
|---:|---:|---:|---:|---:|---:|
| 2 | 2 | 2 | 2 | 2 | 2 |
| 3 | 2 | 2 | 6 | 3 | 6 |
| -2 | 6 | 3 | -2 | -12 | 6 |
| 4 | -2 | -12 | 4 | -48 | 6 |

The negative `-2` destroys the running maximum but creates a much smaller negative product, which is exactly why the minimum track is necessary.

Dry run / state trace

Track the largest and smallest products ending at each index; one pass gives `O(n)` time and `O(1)` space.