Maximum Product Subarray

Given an integer array, your task is to find a contiguous subarray (containing at least one element) which has the largest product, and output its product.

You can solve this problem using a dynamic programming approach. At each index, maintain two values: the maximum product max_prod and the minimum product min_prod ending at that index. When a negative number is encountered, the roles of max_prod and min_prod swap because a large negative number multiplied by a negative value can become positive.

This recurrence can be expressed in \(\LaTeX\) as follows:

\(max\_prod = \max(num, max\_prod \times num)\)

\(min\_prod = \min(num, min\_prod \times num)\)

The final answer is the maximum value among all max_prod values.

inputFormat

The first line contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers representing the array elements.

outputFormat

Print a single integer, which is the maximum product that can be obtained from any contiguous subarray of the given array.## sample

4
2 3 -2 4

6