MAXPROD-Editorial

PROBLEM LINK:

Practice
Contest
In case the contest did not have two separate pages for Div-1 and Div-2, you can delete one of these above lines.

Author: Setter’s name
Tester: Tester’s name

DIFFICULTY:

MEDIUM

PREREQUISITES:

Greedy.

PROBLEM:

In the given question there are n identical isolated containers ranging temperature from -100 to 100 including absolute zero. Chef wants to know the product of the maximum Product subarray of containers.

QUICK EXPLANATION:

You can simply check if n is equal to 1 and A[0] is negative then we have to return A[0]. otherwise, we have to assume Output is always greater than or equal to 0.

EXPLANATION:

The only thing to note here is, the maximum product can also be obtained by the minimum (negative) product ending with the previous element multiplied by this element.
For example, in array {12, 2, -3, -5, -6, -2}, when we are at element -2, the maximum product is the multiplication of, minimum product ending with -6 and -2.

ALTERNATE EXPLANATION:

The idea is to traverse over every contiguous subarray, find the product of each of these subarrays and return the maximum product from these results.

We cannot do this because it gives you WA

The issue is that you are doing a prefix product of the array which is stored in the variable, currentProduct.
This value might overflow for certain test cases.
While the test cases are made such that the max product will never overflow, the overall subarray product might overflow from the negative end.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std; 
long long maxSubarrayProduct(int arr[], int n)
{
	long long  max_ending_here = 1;
	long long min_ending_here = 1;
	long long  max_so_far = 0;
	int flag = 0;
	for (long long i = 0; i < n; i++)
	{
		if (arr[i] > 0) 
		{
			max_ending_here = max_ending_here * arr[i];
			
				if((min_ending_here * arr[i])>0)
				{
					min_ending_here=1; 
				}
				else
				{
					min_ending_here=min_ending_here * arr[i];
				}
			flag = 1;
		}			
		else if (arr[i] == 0) {
			max_ending_here = 1;
			min_ending_here = 1;
		}   	 
		else {
			long long  temp = max_ending_here;
		   
				if((min_ending_here * arr[i])>1)
				{
					max_ending_here=min_ending_here * arr[i];
				}
				else
				{
					max_ending_here=1;
				}
			min_ending_here = temp * arr[i];
		}
		if (max_so_far < max_ending_here)
			max_so_far = max_ending_here;
	}
	if (flag == 0 && max_so_far == 0)
		return 0;
	return max_so_far;  
}
int main()
 {
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		int A[n];
		for(int  i=0;i<n;i++)
		{
			cin>>A[i];
		}
		long long z;
		if(n==1)
		{
			cout<<A[0]<<endl;
		}
		else
		{
			z=maxSubarrayProduct(A,n);
		cout<<z<<endl;
		}
	}
	return 0;
}
Tester's Solution
def maxSubarrayProduct(arr, n):
	result = arr[0]
	for i in range(n):
		mul = arr[i]
		for j in range(i + 1, n):
			result = max(result, mul)
			mul *= arr[j]
		result = max(result, mul)
	 
	return result
 
def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int,input().split()))
		print(maxSubarrayProduct(a,n))
		
if name =="_main_":
	main()