Maximum Product Subarray

Given an integer array \(nums\), find the contiguous subarray within the array (containing at least one number) which has the largest product, and return that product.

The solution should be implemented by reading input from stdin and writing the result to stdout. The input format is as follows:

• The first line contains a single integer \(N\) denoting the number of elements in the array.
• The second line contains \(N\) space-separated integers representing the array elements.

The output consists of a single integer — the maximum product of any contiguous subarray.

One common approach is to use dynamic programming where for each position you keep track of both the maximum and minimum products (since a negative number can turn a small product into a maximum when multiplied). The recurrence can be summarized as:

\[ \text{current\_max} = \max(\text{num}, \text{num} \times \text{current\_max}, \text{num} \times \text{current\_min}) \] \[ \text{current\_min} = \min(\text{num}, \text{num} \times \text{current\_max}, \text{num} \times \text{current\_min}) \]

and then update the global maximum accordingly.

inputFormat

The first line of input contains an integer \(N\) (\(1 \leq N \leq 10^5\)) representing the number of elements in the array. The second line contains \(N\) space-separated integers each in the range of \(-10^9\) to \(10^9\).

outputFormat

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

## sample

4
2 3 -2 4

6