You are given an array arr[] with n elements. Write a program to find the contiguous subarray which has the largest product.

Problem Note

• A contiguous subarray of an array arr[] of length n is a contiguous segment from arr[i] through arr[j] where 0<= i <= j <= n.
• Array arr[] may contain both positive and negative integers. If the array contains all non-negative numbers, the maximum subarray is the product of the entire array.

Example 1

Input: arr[] = [9, -6, 10, 3] 
Output: 30 
Explanation: The subarray [10, 3] has the maximum product.

Example 2

Input: arr[] = [6, -3, -10, 0, 2] 
Output: 180  
Explanation: The subarray [6, -3, -10] has the maximum Product.

Example 3

Input: arr[] = [-2, -3, 0, -2, -40] 
Output:  80  
Explanation: The subarray [-2, -40] has the maximum product.