Maximum Product Subarray

Given an array of integers arr, identify the contiguous segment within the array (with at least one element) that produces the highest product of its elements.

Examples

Example 1:
Input: [3, 2, -4, 5]
Output: 10
Explanation: The subarray [3, 2] has the maximum product 6.

Example 2:
Input: [-3, 0, -2]
Output: 0
Explanation: The maximum product is 0, as subarray [-3, -2] is not contiguous.

Example 3:
Input: [1, -2, -3, 4]
Output: 24
Explanation: The subarray [-2, -3, 4] yields the largest product 24.

Constraints

• 1 ≤ arr.length ≤ 10,000
• -15 ≤ arr[i] ≤ 15