QUESTION
Given an array that contains both positive and negative integers, find the product of the maximum product subarray.\nAssumption: There is always a positive product possible, i.e., no array of this form: {0,-20,0,0} or {-20}.\n\nInput:\nFirst line of input contain number of test cases T. First line of test case contain the size of array and second line of test case contain the array elements.\n\nOutput:\nMaximum product of subarray is displayed to the user.\n\nConstraints:\n1 <=T<= 50\n1 <=N<= 9\n-10 <=arr[i]<= 10.
“TESTCASE_1”: “3\n5\n6 -3 -10 0 2\n6\n2 3 4 5 -1 0 \n10\n8 -2 -2 0 8 0 -6 -8 -6 -1\n###—###SEPERATOR—###—\n180\n120\n288”, “TESTCASE_2”: “2\n5\n2 4 6 8 10\n6\n0 1 2 3 4 5 \n###—###SEPERATOR—###—\n3840\n120”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0
ANSWER
// C program to find Maximum Product Subarray
#include <stdio.h>
// Utility functions to get minimum of two integers
int min (int x, int y) {return x < y? x : y; }
// Utility functions to get maximum of two integers
int max (int x, int y) {return x > y? x : y; }
/* Returns the product of max product subarray.
Assumes that the given array always has a subarray
with product more than 1 */
int maxSubarrayProduct(int arr[], int n)
{
// max positive product ending at the current position
int max_ending_here = 1;
// min negative product ending at the current position
int min_ending_here = 1;
// Initialize overall max product
int max_so_far = 1,i;
/* Traverse through the array. Following values are
maintained after the i'th iteration:
max_ending_here is always 1 or some positive product
ending with arr[i]
min_ending_here is always 1 or some negative product
ending with arr[i] */
for (i = 0; i < n; i++)
{
/* If this element is positive, update max_ending_here.
Update min_ending_here only if min_ending_here is
negative */
if (arr[i] > 0)
{
max_ending_here = max_ending_here*arr[i];
min_ending_here = min (min_ending_here * arr[i], 1);
}
/* If this element is 0, then the maximum product
cannot end here, make both max_ending_here and
min_ending_here 0
Assumption: Output is alway greater than or equal
to 1. */
else if (arr[i] == 0)
{
max_ending_here = 1;
min_ending_here = 1;
}
/* If element is negative. This is tricky
max_ending_here can either be 1 or positive.
min_ending_here can either be 1 or negative.
next min_ending_here will always be prev.
max_ending_here * arr[i] next max_ending_here
will be 1 if prev min_ending_here is 1, otherwise
next max_ending_here will be prev min_ending_here *
arr[i] */
else
{
int temp = max_ending_here;
max_ending_here = max (min_ending_here * arr[i], 1);
min_ending_here = temp * arr[i];
}
// update max_so_far, if needed
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}
// Driver Program to test above function
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,i;
scanf("%d",&n);
int arr[n];
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
printf("%d\n",
maxSubarrayProduct(arr, n));
}
return 0;
}