To find the maximum product subarray, we need to understand how multiplication behaves with different types of numbers. Unlike sum problems, multiplication is tricky because of negatives and zeros.
Key Observations
- Multiplying a negative with another negative becomes positive.
- Zero resets the product (anything multiplied by 0 becomes 0).
- We are interested in the maximum product, which can be hidden between negative values or split by zeros.
How We Approach the Problem
We scan the array from left to right, and at each position, we maintain two values:
- max_product: the maximum product ending at that index
- min_product: the minimum product ending at that index (important for handling negatives)
If we encounter a negative number, we swap max and min because a large negative times a negative could become the new maximum.
If we encounter a zero, we reset both max and min to zero (or start fresh from the next element).
At every step, we update our final result with the highest max_product seen so far.
📦 Case-by-Case Explanation
- All positives: The maximum product is the product of the whole array.
- All negatives with even count: Product of the whole array will be positive and maximum.
- All negatives with odd count: Exclude one negative (whichever gives max).
- Zeros present: Treat zeros as split points; maximum product may lie in segments between them.
- Single element array: That element is the maximum product.
- Empty array: No product is possible, so return 0.
🎯 Final Thoughts
This is a classic example of using dynamic programming to track values at each step. The key trick is keeping both min and max products because negatives can flip roles. This approach ensures we always find the best subarray in O(n) time.