81. Maximum Product Subarray

Given integer array nums, find the subarray with the largest product and return the product.

Input: Integer array nums.

Output: Maximum product of any contiguous subarray.

Examples

Example 1

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has product 6.

Example 2

Input: [-2,0,-1]
Output: 0
Explanation: Best subarray is [0].

Example 3

Input: [-2,-3,-4]
Output: 12
Explanation: [-3,-4] gives 12.