Maximum Product Subarray

Problem Description:

Given an array of integers, your task is to find the maximum product of any contiguous subarray. In other words, if you are given an array (A = [a_1, a_2, \dots, a_n]), you need to determine the maximum value of (\prod_{i=l}^{r} a_i) for some indices (1 \le l \le r \le n).

Notice that the array can contain positive numbers, negative numbers, and zeros, which makes the problem challenging. The presence of negative numbers can turn a small product into a large one when multiplied, and a zero will reset the product calculation. Thus, careful handling of current maximum and minimum products during iteration is required.

Your solution should read the input from standard input (stdin) and output the result to standard output (stdout) as a single integer.

inputFormat

Input Format:

The first line contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers (a_1, a_2, \dots, a_n).

outputFormat

Output Format:

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

5
2 3 -2 4 -1

48