Maximum product subarray in a given array in C

October 13, 2021

Maximum product of sub-array IN C

Find the maximum product subarray in a given array in C

In this article, we will brief in on how to find the maximum product subarray of a given array .We will perform task to find the subarray from the given input array whose product is maximum . It will help us find the contiguous sub-array with atleast one element which has the largest product.

Algorithm

  1. Enter the elements.
  2. If array[0] > 0
  3. maximum = array[k]
  4. Initialize maximum_so_far = array[k].
  5. Repeat from k = 1 till the end .
  6. Multiply maximum with the next array element if it is positive
  7. Update maximum = max_so_far.
  8. Else,skip the array element 
  9. Move to the next array element.
  10. Return max_so_far.

C Code Based on above algorithm

#include<stdio.h>
int minimum (int m, int n)
{
  return m < n ? m : n;
}

int maximum (int m, int n)
{
  return m > n ? m : n;
}

int maxSubarrayProduct (int arr[], int a)
{
  int max_ending_here = 1;
  int min_ending_here = 1;
  int MAXIMUM = 1;
  for (int i = 0; i < a; i++)
    {
      if (arr[i] > 0)
	{
	  max_ending_here = max_ending_here * arr[i];
	  min_ending_here = minimum (min_ending_here * arr[i], 1);
	}
      else if (arr[i] == 0)
	{
	  max_ending_here = 1;
	  min_ending_here = 1;
	}
      else
	{
	  int temp = max_ending_here;	
	  max_ending_here = maximum (min_ending_here * arr[i], 1);
	  min_ending_here = temp * arr[i];
	}
      if (MAXIMUM < max_ending_here)
	MAXIMUM = max_ending_here;
    }
  return MAXIMUM;
}
int main ()
{
  int length;
  printf ("Enter the size: ");
  scanf ("%d", &length);
  int array[10];
  printf ("Enter the elements : ");
  for (int i = 0; i < length; i++)
    scanf ("%d", &array[i]);\
  printf ("Maximum product : %d", maxSubarrayProduct (array, length));
  return 0;

}
Input:

Enter the size: 6
Enter the elements : 9 6 3 4 8 2

Output:
Maximum product : 10368