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)**.