Maximum Product Subarray

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro