# LeetCode 152: Maximum Product Subarray — Step-by-Step Visual Trace

**Medium** — Dynamic Programming | Array | Kadane's Algorithm

## The Problem

Find the contiguous subarray within an array of integers that has the largest product and return that product.

## Approach

Use dynamic programming to track both maximum and minimum products at each position, swapping them when encountering negative numbers. This handles the case where negative numbers can turn a small product into a large one.

**Time:** O(n) · **Space:** O(1)

## Code

```python
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # Initialize variables to keep track of the maximum and minimum product ending at the current position.
        max_product = min_product = result = nums[0]

        # Iterate through the array starting from the second element.
        for i in range(1, len(nums)):
            # If the current element is negative, swap max_product and min_product
            # because multiplying a negative number can turn the maximum into the minimum.
            if nums[i] < 0:
                max_product, min_product = min_product, max_product

            # Update max_product and min_product based on the current element.
            max_product = max(nums[i], max_product * nums[i])
            min_product = min(nums[i], min_product * nums[i])

            # Update the overall result with the maximum product found so far.
            result = max(result, max_product)

        return result
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0152_maximum-product-subarray)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0152_maximum-product-subarray) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*