Maximum Product Subarray

Given an array of integers, determine the contiguous subarray (containing at least one number) that has the largest product, and output this product. Note that the subarray must consist of consecutive elements. This problem is complicated by the fact that the product of two negative numbers yields a positive result, and zeros can reset the product calculation. Formally, you are to maximize the expression $$\max_{1 \le i \le j \le n} \prod_{k=i}^{j}a_k,$$ where \(a_k\) represents the elements of the array.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(n\), the number of elements in the array. The second line contains \(n\) space-separated integers representing the array elements.

outputFormat

Output a single integer to standard output (stdout) which is the maximum product of any contiguous subarray.

1
3

3