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;
}