23. Find Maximum Product Subarray

Given an array of integers (which may include negatives and zeros), find the maximum product achievable from any contiguous subarray. Print that product.

Input: The first line contains an integer n. The second line contains n space-separated integers, which may include negative numbers and zeros. Output: Print a single integer - the maximum product obtainable from any contiguous subarray.

1 <= n <= 10^5

A zero anywhere in the array acts as a hard reset - no product streak can ever cross over a zero, so the running trackers must restart cleanly right after one.

Find the contiguous stretch of an array (which may include negatives and zeros) that multiplies together to the biggest possible product. Brute force: Check every possible contiguous subarray directly, computing its product - this costs O(n²), too slow for large arrays, and also risks numeric overflow if not handled carefully. Optimised: Tracking BOTH a running max and a running min (not just a max, unlike Kadane's sum version) is the crucial adaptation needed for products, since multiplying two negative numbers flips a bad running minimum into a great new maximum - this dual tracking lets a single linear pass correctly account for that sign-flipping behavior.

Scan left to right building a running product that resets to 1 immediately after hitting a zero, tracking the maximum value seen at every position (this is the prefix product array); then do the same scanning right to left (the suffix product array). The true answer must appear in one of these two arrays because any maximal zero-free segment's best product is captured by looking at it from one end or the other, since a negative-heavy segment's best subarray excludes either its very first or very last element. Time: O(n) Space: O(n)

Compute the product of every contiguous subarray directly by iterating over all start and end index pairs, multiplying elements as the end index extends, and tracking the running maximum seen. This checks every subarray explicitly, so it is correct but redundantly recomputes overlapping products. Time: O(n^2) Space: O(1)

Walk through the array once maintaining both the maximum and minimum product ending at the current position, since a negative number can turn the smallest (most negative) running product into the new largest one. At each step compute the candidate new max/min from the current element times the previous max, times the previous min, or the element alone, and update the global answer, which avoids the two full extra passes and any auxiliary arrays. Time: O(n) Space: O(1)

1. Unlike a sum, a product can flip sign entirely from one bad negative number - so track BOTH a running maximum product ending here AND a running minimum product ending here (since a very negative running minimum, multiplied by another negative, can suddenly become the new maximum). 2. At each element, compute the three candidates: the element alone, the element times the previous running max, and the element times the previous running min - the new running max and running min are the biggest and smallest of these three. 3. Track the overall best running max seen across the whole scan. 4. Reset both running trackers whenever you cross a zero, since a zero breaks any ongoing product streak entirely.

Time: O(n) - one single pass through the array. Space: O(1) - just the two running trackers (max and min) plus the overall best answer.

Test n = 1, arrays containing zeros (which reset the running product) and an even count of negatives that flips into a large positive product, and n = 10^5 for performance.

Be ready to explain clearly why a running MINIMUM is needed at all (unlike the pure-sum version, Kadane's algorithm) - this is exactly the insight interviewers are testing when they ask this as a 'harder version of Kadane's' follow-up.