Given an array Arr[] that contains N integers (may be positive, negative or zero). Find the product of the maximum product subarray.

Example 1:

Input:
N = 5
Arr[] = {6, -3, -10, 0, 2}
Output: 180
Explanation: Subarray with maximum product
is [6, -3, -10] which gives product as 180.

Example 2:

Input:
N = 6
Arr[] = {2, 3, 4, 5, -1, 0}
Output: 120
Explanation: Subarray with maximum product
is [2, 3, 4, 5] which gives product as 120.

Your Task:
You don't need to read input or print anything. Your task is to complete the function maxProduct() which takes the array of integers arr and n as parameters and returns an integer denoting the answer.
Note: Use 64-bit integer data type to avoid overflow.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N ≤ 500
-10² ≤ Arr_i ≤ 10²

Explanation:

This is an explanation of the approach to solve a problem related to finding the maximum product subarray in an array, which is often asked in technical coding rounds during the hiring process. The approach involves understanding four conditions to solve the problem effectively.

The first condition is when all elements in the array are positive. For example, if we take an array such as [2, 2, 3, 4, 5], we can multiply all the elements together to get the maximum multiplication.

The second condition is when there are an even number of negative elements in the array. For instance, if we take an array like [2, -2, -3, 4, 5], we can multiply all the elements together to get the maximum multiplication.

The third condition is when the array contains an odd number of negative elements. For instance, if we take an array like [2, -2, 3, -4, 5, 6, -7, 1], there are two possible scenarios to consider. First, we can take -2 as the middle point and get [2] and [3, -4, 5, 6, -7, 1]. Second, we can take -7 as the middle point and get [2, -2, 3, -4, 5, 6] and [-7, 1].

The fourth condition is when the array contains zeros. When we multiply any number with 0, the multiplication becomes zero. Hence, when a zero appears in the array during traversal, we initialize prefix_product and suffix_product to 1.

Solution:

class Solution {
    // Function to find maximum product subarray
    long maxProduct(int[] arr, int n) {


        long pref = 1;
        long suf = 1;
        long ans = Integer.MIN_VALUE;

        for(int i=0; i<n; i++)
        {
            if(pref == 0)
                pref=1;
            if(suf == 0)
                suf=1;

            pref = pref * arr[i];
            suf = suf* arr[n-i-1];

            ans = Math.max(ans, Math.max(pref, suf));
        }

        return ans;
    }
}