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 lengthn
is a contiguous segment fromarr[i]
througharr[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.