# Maximum Product Subarray

- **Canonical ID**: `maximum-product-subarray`
- **Canonical URL**: https://dsacheatsheet.com/problems/maximum-product-subarray
- **Difficulty**: medium
- **Patterns**: 1D DP
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/maximum-product-subarray/

## 1. Core Invariant / The Trick

Because multiplying by a negative swaps maximum and minimum signs (and multiplying by `0` resets products), track **both** `(curMax, curMin)` ending at `i`: update simultaneously against `x`, `curMax * x`, and `curMin * x`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Constant state `(curMax, curMin)` per step visits each number once.

## 3. Minimal Idiomatic Code

### Python
```python
def maxProduct(nums: list[int]) -> int:
    best = cur_max = cur_min = nums[0]
    for x in nums[1:]:
        a, b = cur_max * x, cur_min * x
        cur_max = max(x, a, b)
        cur_min = min(x, a, b)
        best = max(best, cur_max)
    return best
```

### TypeScript
```typescript
export function maxProduct(nums: number[]): number {
  let best = nums[0], curMax = nums[0], curMin = nums[0];
  for (let i = 1; i < nums.length; i++) {
    const x = nums[i], a = curMax * x, b = curMin * x;
    curMax = Math.max(x, a, b);
    curMin = Math.min(x, a, b);
    best = Math.max(best, curMax);
  }
  return best;
}
```

### C++
```cpp
int maxProduct(vector<int>& nums) {
    int best = nums[0], cmax = nums[0], cmin = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
        int x = nums[i], a = cmax * x, b = cmin * x;
        cmax = max({x, a, b});
        cmin = min({x, a, b});
        best = max(best, cmax);
    }
    return best;
}
```

### Java
```java
int maxProduct(int[] nums) {
    int best = nums[0], cmax = nums[0], cmin = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int x = nums[i], a = cmax * x, b = cmin * x;
        cmax = Math.max(x, Math.max(a, b));
        cmin = Math.min(x, Math.min(a, b));
        best = Math.max(best, cmax);
    }
    return best;
}
```

### Go
```go
func maxProduct(nums []int) int {
    best, cmax, cmin := nums[0], nums[0], nums[0]
    for _, x := range nums[1:] {
        a, b := cmax*x, cmin*x
        cmax = max(x, max(a, b))
        cmin = min(x, min(a, b))
        best = max(best, cmax)
    }
    return best
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Clobbering `curMax` before computing `curMin` corrupts the negative-flip product (`save prevMax = curMax` or unpack tuple).
- Single-element negative array `[-3]` returns `-3`.

### Follow-ups
- Prefix-and-suffix pass computes products forward and backward resetting on `0`; the answer lies in one pass when negative count is even/odd.