Maximum Product Subarray

Find the largest product of a non-empty contiguous subarray.

Input:

• line 1: n
• line 2: n integers

Output: the maximum product.

Constraints: 1 ≤ n ≤ 10⁵, −10 ≤ a[i] ≤ 10. Every subarray's product fits in a signed 64-bit integer.

Think about it: a negative number turns the smallest product into the largest. So track both the maximum and the minimum product ending at each position; at x, the new values come from x, max·x and min·x. Zeros reset everything.