Maximum Product Subarray

Problem Find the contiguous subarray with the largest product and return the product. The array contains positives, negatives, and zeros.

Input / Output

• Input: int array nums. Output: max product over all subarrays.

Constraints

• 1 <= n <= 2*10^4; product fits in 32 bits per the classic constraints; O(n) expected.

Example

• [2,3,-2,4] → 6 ([2,3]); [-2,0,-1] → 0; [-2,3,-4] → 24 (whole array).