Maximum Product Subarray

Given an array of integers, your task is to find the contiguous subarray within the array (containing at least one number) that has the largest product, and output this product.

For example, consider the array: [2, 3, -2, 4]. The contiguous subarray with the maximum product is [2, 3] and its product is 6.

The problem can be formulated mathematically as follows:

Given an array \(A = [a_1, a_2, \dots, a_n]\), find indices \(i\) and \(j\) with \(1 \le i \le j \le n\) such that the product \[ P = \prod_{k=i}^{j} a_k \] is maximized.

inputFormat

The input is read from standard input and is formatted as follows:

1. The first line contains a single integer \(n\) representing the number of elements in the array.
2. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer: the maximum product achieved by any contiguous subarray of the given array.

4
2 3 -2 4

6