Understanding the Problem
We are given an array of integers. Our goal is to find the maximum product subarray — that is, the contiguous subarray that gives the largest product when its elements are multiplied together.
Unlike sum problems, multiplication has unique challenges:
- Multiplying two negative numbers gives a positive number.
- Multiplying any number with zero resets the product to zero.
- Negative numbers can reduce the product or, if paired well, create the maximum one.
Step-by-Step Solution Using Example
Example: nums = [2, 3, -2, 4]
We go through the array one element at a time. At each step, we keep track of:
- maxProductEndingHere: The maximum product that ends at the current index.
- minProductEndingHere: The minimum product that ends at the current index.
This is important because a negative number might make a small (even negative) product become a large positive one when multiplied.
Step-by-step execution:
- Start with max = min = result = 2 (first number)
- Next, 3:
- tempMax = max(3, 2*3, 2*3) = 6
- tempMin = min(3, 2*3, 2*3) = 3
- Update result = max(6, 2) = 6
- Next, -2:
- tempMax = max(-2, 6*(-2), 3*(-2)) = max(-2, -12, -6) = -2
- tempMin = min(-2, 6*(-2), 3*(-2)) = min(-2, -12, -6) = -12
- Swap min and max because of negative
- Update result = max(6, -2) = 6
- Next, 4:
- tempMax = max(4, -2*4, -12*4) = max(4, -8, -48) = 4
- tempMin = min(4, -2*4, -12*4) = min(4, -8, -48) = -48
- Update result = max(6, 4) = 6
Final Answer = 6
Edge Case Handling
What happens in special cases?
- Array contains 0: Restart max and min at 0; product splits.
- All positive: Product of full array is maximum.
- All negative (even count): Product of entire array is maximum (negatives cancel).
- All negative (odd count): Drop one negative (either from start or end) to get maximum product.
- Single element: That is the result.
- Empty array: No subarray exists. Return 0.
Key Intuition for Beginners
- We are not just tracking the max product — we also track the min because it can become max after a negative.
- Think of zero as a wall. You can’t continue the product across it.
- Swapping min and max when we see a negative is a key trick.
Finally
This is a classic dynamic programming problem. At each step, you use previous results to decide your current best. You only need one pass through the array, so the time complexity is O(n).
By managing both the maximum and minimum product ending at each position, we can smartly deal with negatives and zeros to find the optimal subarray product.
Comments
Loading comments...