Maximum Product Subarray

You are given an array of n integers which can contain positive, negative, and zero values. Your task is to find the contiguous subarray (containing at least one number) which has the largest product and output that product.

The solution should have a time complexity of \(O(n)\). This means that you should be able to solve the problem by iterating through the array only once.

Example:

• For the input array: [2, 3, -2, 4, -1], the maximum product is 48.
• For the input array: [1], the maximum product is 1.
• For the input array: [-1], the maximum product is -1.

More examples are provided in the test cases.

inputFormat

The first line of input contains a single integer n denoting the number of elements in the array.

The second line contains n space-separated integers which represent the elements of the array.

outputFormat

Output a single integer which is the maximum product of any contiguous subarray.

5
2 3 -2 4 -1

48