Question
Maximum Product Subarray
You are given an array of integers. Your task is to find a contiguous subarray that has the maximum possible product, and print the value of that product.
A subarray must contain at least one element and must consist of consecutive elements from the array.
The test cases are generated so that the answer will fit in a 64-bit integer.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the size of the array.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression — representing the elements of the array.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression — representing the elements of the array.
Output
Print a single integer — the maximum product of any contiguous subarray.
Example
Input
4
2 3 -2 4
Output
6
Explanation
The subarray KaTeX can only parse string typed expression has product:
KaTeX can only parse string typed expression
No other contiguous subarray has a larger product.
Input
3
-2 0 -1
Output
0
Explanation
Possible subarray products include:
KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression.
The maximum product among all subarrays is KaTeX can only parse string typed expression.
4
2 3 -2 4
Output
6
Explanation
The subarray KaTeX can only parse string typed expression has product:
KaTeX can only parse string typed expression
No other contiguous subarray has a larger product.
Input
3
-2 0 -1
Output
0
Explanation
Possible subarray products include:
KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression.
The maximum product among all subarrays is KaTeX can only parse string typed expression.