Maximum Product Subarray

Given an array of integers, find the contiguous subarray within the array (containing at least one number) which has the largest product.

For an array ( nums ) of length ( n ), a contiguous subarray is a sequence ( nums[i], nums[i+1], \ldots, nums[j] ) where ( 0 \leq i \leq j < n ). The task is to compute the maximum product that can be achieved by any such subarray.

The optimal solution should run in linear time ( O(n) ) and use constant extra space. Consider both positive and negative numbers, and remember that the product of two negative numbers is positive. Also, note that the presence of zero may reset the product sequence.

inputFormat

The first line contains an integer ( n ) ((1 \le n \le 10^5)) representing the number of elements in the array. The second line contains ( n ) integers separated by spaces, where each integer ( nums[i] ) ((|nums[i]| \le 10^9)) is an element of the array.

outputFormat

Output a single integer which is the maximum product of a contiguous subarray of the array.## sample

5
2 3 -2 4 -1

48