Maximum Product Subarray – Solution & Complexity

• 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.

• 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.

• 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.

• 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.

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

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

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