Given an integer array arr[] that contains n integers (positive, negative or zero).
The task is to find a contiguous non-empty subarray within the array that has the largest product.
Input: 2,3,-2,4
Output: 6
Input: 6, -3, -10, 0, 2
Output: 180
Solutions
Method 1: Modified Kadane's Algorithm
This approach is similar to the Largest sum contiguous sub-array (Kadane's Algorithm).
The only thing to keep in mind here is that a negative minimum product ending with the previous element multiplied by the current element (if negative) can also yield a maximum product.
Therefore, we need to maintain an extra variable "min_ending_here" to store the minimum product, along with "max_ending_here" and "max_so_far".
For every iteration, the maximum number ending at that index will be the maximum(arr[i], max_ending_here * arr[i], min_ending_here[i]*arr[i]).
Similarly, the minimum number ending here will be the minimum of these 3.
Finally, "max_so_far" will be the maximum of "max_ending_here" and "max_so_far".
This solution works for "all-positive", "all-negative" as well as "positive-negative-zero" combinations.
Complexity
The time complexity of this solution is O(n) and space complexity is O(1).